Wiem, jak ktoś się nie spieszy i stać go na zwarcie krtaniowe, to wymówi.
Po doszczętnym wyczyszczeniu obrazka z zawartości tego, nad czym ostatnio się głowię (jak wiadomo, matematyka to abstrahowanie czyli czyszczenie aż do zaniku) wyszło coś, czym mogę zabawić blogowe wizyty. Nie gwarantuję, że jestem odkrywcą czy autorem takiej kwestii, bo matematyków i innych ścisłowców jest tylu, że się ich nie da przeliczyć, więc może ktoś już to opatentował. Ale wcześniej na to nie wpadłem, choć stykając się z kombinatoryką musiałem i o teorii grafów nieco się pouczyć.
Jest tu 15 osób i między różnymi parami bywają ansy i napięcia. A linie łączące imiona są tego rejestrem.
Zaproponuj skład jak najliczniejszych możliwie grup, które by nie miały wewnętrznych spięć.
Jeśli zrobisz podobny graf dla grupy swoich znajomych, przypuszczalnie zauważysz – tak jak tutaj – że montowanie takiej grupy wcale nie musi zaczynać się od najmniej konfliktowej osoby. Tutaj jest nią Emilia, ma kłopoty tylko z dwoma innymi osobami, ale są możliwe „pokojowe” grupy, do których ona nie należy.
Ciekawi mnie czy łatwo by było opracować algorytm na rozwiązywanie tego problemu mając inną liczbę osób i „negatywnych” połączeń. Łatwe też jest modyfikowanie problemu, np. używając linie ze strzałkami w jedną lub w obie strony.
Miłej zabawy.
Migotanie słów 
Pierwsza myśl z którą ten wpis skojarzyłem: – Czy bieganie wiąże się z niższym ryzykiem zgonów z przyczyn ogólnych, sercowo-naczyniowych?
A druga myśl jaka mi przemknęła, to święta geometria (sacred geometry).
Na wątpliwość: – „czy łatwo by było opracować algorytm na rozwiązywanie tego problemu mając inną liczbę osób i „negatywnych” połączeń” nie odpowiem. To pytanie nie wymaga odpowiedzi, jest zachętą.
Jeśli relacja „mieć anse do” jest symetryczna, to mamy do czynienia z problemem łatwiejszym i socjopsychologicznie mniej realistycznym. X „ma skrytą urazę do” Y, a Y nic o tym nie wie. Albo wie (wtedy skrytość jest stanem subiektywnym), ale wisimuto lub jest, nazwijmy, wielkoduszny.
Na literackie poletko do badania niesymetrycznej wersji tej lub podobnych relacji nominowałbym „Niebezpieczne związki” Choderlosa de Laclosa.
W wariancie symetrycznym odejmujemy do kliki [graf pełny, każde z każdym] siatkans – czyli wymazujemy krawędzie (linie) „ansowe” – a w tym, co zostanie, wyszukujemy najliczniejsze kliki. Połączenie między A i B w grafie po odjęciu oznacza „A nie ma nic do B i odwrotnie”.
Wracając do de Laclosa: socjopsychodynamika grupy. Jeśli grupa, to interakcje, w tym relacje osób trzecich. Hipoteza „Niebezpieczno związkowa” mogłaby być taka, że po dostatecznie dlugim czasie każda relacja „ansowa” symetryzuje się. Wymiar realistyczny – czy wszyscy uczestnicy grupy dożyją.
[*] oczywiście powino być „odejmujemy OD grafu pełnego”
@nameste, rozwiązanie zaiste zwięzłe – problem rozwiązany poprzez sprowadzenie do innego problemu. No ale ten inny problem jakoś wcale łatwiejszy nie jest, nawet dla komputera. https://en.wikipedia.org/wiki/Clique_problem
@nightwatch, istotnie, w ogólnym przypadku mamy ciężej niż ciężko. Ale ratuje nas tutaj dziedzina rozważań: interakcje w grupie ludzkiej. Przypomnę, że za umowną granicę liczności „stada” (czegoś słabiej określonego niż grupa-z-istotnymi-interakcjami) przyjmuje się okolice 150 osobników: powyżej tej liczności zaczyna szwankować rozpoznawanie i zapamiętywanie jednostek (poszerza się sfera „obcych”).
Owszem, sprawę nieco komplikują interakcje via net, ale tam [tu :–)] z kolei wykładniczo wzrasta udział „wisimuto”.
@ nameste – to 150 – jak może wiesz – to liczba Dunbara: https://en.wikipedia.org/wiki/Dunbar%27s_number
Nie chcę bynajmniej uchodzić za erudytę, zbiegiem okoliczności akurat dziś rano się na to natknąłem:
https://www.scmp.com/magazines/post-magazine/long-reads/article/3083098/can-app-make-you-better-friend-personal
@kwik, liczba Dunbara, mogłem kiedyś znać tę nazwę. Co do drugiego linku – chyba tylko dla erudytów ^
Panowie, proszę bez wyzwisk.
macie na myśli jakiś nowy rodzaj erudycji?
Szostka to dobry wynik?
@Hellk, masz lepsze od mojego oko, 6 to celujący.. Dotarłem (bez ambicji znalezienia wszystkich) tylko do piątek:
A,B,E,F,R
B,C,F,K,L
E,F,I,K,R
G,H,I,M,P
Pokaż Twoją szóstkę, proszę.
Ebklfr, (dzis na trzezwo trudniej bylo to odtworzyc niz wczoraj wieczorem zrobic:). Prosze o weryfikacje, bo moglem cos przeoczyc – to zadanie jest troche jak ‚8 krolowych’ 🙂
Mam nadzieję, ze się nie wygłupię ale kojarzę Nasha
@Hellk, masz rację, rozwiązanie z 6 elementami: B,E,F,K,L,R jest poprawne. Gratuluję!
Wolę pisać majuskułami, bo nie ma ryzyka pomieszania minuskuły „el” z majuskułą „i”.
W istocie, to ten sam duch co w zadaniu o 8 nie-atakujących się królowych na szachownicy. Ciekaw jestem czy specjaliści znajdą podobieństwa w technikach rozwiązywania obu zadań.
@jac, o Nashu czytałem książkę, ale jego samego nic, nie znam jego dziedziny działania.
Ja nic nie mam przeciwko wygłupianiu się, sam nie tak rzadko potrafię to robić. Nie lubię natomiast ogłupianie innych. Może dlatego cieszę się, że tych 7 lat temu (a może to było, przedtem, przed 14 laty?) Gab nie przekonał mnie, że warto wrócić do Polski. Wydaje się, że ogłupianie innych staje się najpopularniejszym narodowym sportem.
MPAGHI:)
@Hellk: świetne! Potwierdza moją intuicję, że najmniej konfliktowy element (tutaj: E) nie jest nieodzowny w możliwie najliczniejszej niekofliktowej grupie.