Zadanie, zagadka, graf Opcje

[darektbg]

Spotkałem się kiedyś z zadaniem, o treści:
Są 3 żródła(woda, gaz i prąd) oraz 3 domy Każde ze źródeł musi dotrzeć do każdego domu, zaznaczając linią drogę. Żadna linia nie może się przeciąć, można jednak dowolnie przestawiać obiekty.
(IMG:http://tbgpk.tbg.net.pl/1.JPG)
Przykładowe ‘rozwiązanie’, tylko dla gazu i wody jest poniżej, jednak został jeszcze prąd. Od razu mówie, że rozwiązania nie ma.
(IMG:http://tbgpk.tbg.net.pl/2.JPG)
No i moje pytanie: w jaki sposób można to uzasadnić ?

[darektbg]

tak, można dowolnie przestawiać, tak aby tylko sens połączeń został zachowany(każde żródło do każdego domu)

EDIT
Doszedłem do wniosku, że gdyby rozwiązanie było możliwe, to przedstawiony układ byłby grafem, więc należy sprawdzić czy dany graf isteniej.

Przedstawiony tutaj algorytm oparty jest o twierdzenie P. Erdos, T. Gallai z 1960 roku, które mówi, iż podział liczby 2k na n części c1 ≥ c2 ≥ ... ≥ cn jest podziałem graficznym wtedy i tylko wtedy, gdy dla każdej liczby całkowitej j z przedziału od 1 do n-1 jest spełniona nierówność.
(IMG:http://algorytm.org/images/stories/ag/graficzny_1.gif)

Ten post edytował darektbg 13.05.2007, 19:43:52