Forum absolwentów klasy 3F ILO

to tak mam uzasadnienie dla zadania Kury, to na temat 3 domków, gazu, prądu i wody. Sam niemogłem znaleźć rozwiązania to zapytałem dr. Dobreńko. a on udzielił pisemnej odpowiedzi na zadanie. ( ja i piotr mieliśmy racje że nie możliwe jest połączenie tego) jedynym skrajnym rozwiązaniem jest połączenie pradu w szegeru zamknietym przez wszystkie domki a gaz i wode połączyć oddielnie do każdego. a uzasadnienie dlaczego nie można połączyć tego tak jak jest założone przez niektórych (patrz=> nieprzecinają się, i wszystko oddzielnie jest łączone). 

to tak.. domki z mediami tworza graf pełny dwudzielny oznaczany K3,3 to znaczy.. elementy ze zbiorow {domek1 , domek 2, domek 3} i zbioru {gaz, prad, woda} sa polaczone tak ze "kazdy z kazdym" czyli wynikowo tworza iloczyn kartezjanski..  Istnieje twierdzenie ze.. "Graf jest planarny wtedy i tylko wtedy nie zawiera podgrafu homeomorficznego z grafem K5 lub K3,3"

w skrócie.. jezeli w grafie mozna sciagnac krawedzie do K5 lub K3,3 to w takim grafie musze sie przeciac krawedzie..jezeli tak nie jest.. to graf jest planarny..czyli.. taki w ktorym krawedzie nie przecinaja sie..maksymalny pelny dwudzielny planarny jest K2,3.

Jeżeli ktoś nie wie co to jest iloczyn kartezjański to może zobaczyć definicje w necie, może być na wikipedii tak myśle.