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ć ?

[empathon]

Dla przestrzeni n=2 każde dwa dojścia dzielą płaszczyznę na dwie półpłaszczyzny. Po prostu przestrzeń jest za ciasna. Kombinuj chyba w tym kierunku. To tak samo jak z unifikacją praw fizyki w n=4 (IMG:http://forum.php.pl/style_emoticons/default/winksmiley.jpg)

Edit:
Hmm jednak nie źle napisałem.
A można przestawiać źródła z odbiornikami?

Ten post edytował empathon 13.05.2007, 19:35:05

[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

[Jabol]

To jest tak, że jak masz trzy domy i dwa źródła i połączysz każdy dom z obydwoma źródłami, to dostajesz figurę w której jeden z domów jest "zamknięty" pomiędzy połączeniami dwóch pozostałych domów. Jego własne połączenia dzielą figurę z pozostałych połączeń na dwa. Czyli mamy trzy płaszczyzny - każda przylega do dwóch domów, dwóch źródeł i czterech połączeń. Musimy teraz w jakieś płaszczyźnie umieścić trzecie źródło tak aby ta płaszczyzna przylegała do trzech domów. I tego się nie da bo mamy sytuacje opisaną powyżej. Proste, aczklowiek nie wiem czy wystarczające na dowód matematyczny (choć jakby to opisać i dodać przykłady to pewno by starczyło).

Ten post edytował Jabol 13.05.2007, 19:44:23

[tiraeth]

http://pl.wikipedia.org/wiki/Graf_planarny

http://en.wikipedia.org/wiki/Water%2C_gas%2C_and_electricity

Wyjaśnień nie wymaga...

[mls]

Hehe, zagadka jest o tyle ciekawa, że nawet ma swoją wersję w sieci - http://www.supuzzle.com/ (IMG:http://forum.php.pl/style_emoticons/default/smile.gif)