Siatkans

To są dwa słowa: „siatka ans”, ale nie da się tego wymówić, a nie bawi mnie zmiana tytułu – na przykład na „siatka uraz”, bo robi się jakieś „auuu!” a chodzi o ludzi, nie o inne ssaki.

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.

16 myśli na temat “Siatkans

  1. 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ą.

  2. 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ą.

  3. @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”.

  4. @kwik, liczba Dunbara, mogłem kiedyś znać tę nazwę. Co do drugiego linku – chyba tylko dla erudytów ^

  5. @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ę.

  6. 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’ 🙂

  7. @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.

  8. @Hellk: świetne! Potwierdza moją intuicję, że najmniej konfliktowy element (tutaj: E) nie jest nieodzowny w możliwie najliczniejszej niekofliktowej grupie.

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj /  Zmień )

Zdjęcie na Google

Komentujesz korzystając z konta Google. Wyloguj /  Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj /  Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj /  Zmień )

Połączenie z %s