3 domki...

khorh · Post autor: **khorh** » 8 lis 2006, o 18:45

Nie jestem pewien czy da sie to zadanie rozwiązać

Mamy 3 domki i 3 punkty (prąd, woda, gaz). Należy połączyć liniamy prąd wodę i gaz do każdego z domków ale linie NIE mogą się przecinać.

PanCiasteczko · Post autor: **PanCiasteczko** » 8 lis 2006, o 18:57

a ta zagadka ma byc w 3D czy 2D ?

Calasilyar · Post autor: **Calasilyar** » 8 lis 2006, o 21:18

znając życie 2D

khorh · Post autor: **khorh** » 8 lis 2006, o 21:35

w 3d to by nie bylo problemu nie ma tak latwo, mi cos sie zdaje ze to jednak nie do rozwiazania jest, zawsze brakuje jednej linki do domku doprowadzic jednego...

qsiarz · Post autor: **qsiarz** » 8 lis 2006, o 23:53

cos takiego obleci?

khorh · Post autor: **khorh** » 9 lis 2006, o 08:13

nie, bo wyprowadziles linie z domkow...

probowalem sam nawet przestawiać te punkty i też zawsze brakuje dla 1 żyły miejsca...

yorgin · Post autor: **yorgin** » 11 lis 2006, o 16:16

Nie pamietam dokladnie, ale w teorii grafow istnieje cos takiego jak liczba węzłów, czyli ilość przecieć się krzywych prowadzonych od m do n punktów, tak by każdy punkt z m był połączony z n punktami. Zgodnie ze wzorem, którego nie pamiętam niestety , minimalna liczba węzłów wynosi 1, czyli danego tu zadania nie da się rozwiązać.

Ma niewiedza i brak odpowiedniej ksiązki sprawia ze nie opieram sie na konkretach tylko na tym co pamietam.

Pimpek · Post autor: **Pimpek** » 15 lis 2006, o 20:46

minimalnie musi być jedno przecięcie

Undre · Post autor: **Undre** » 15 lis 2006, o 23:29

nie musi być już widzę rozwiązanie

khorh · Post autor: **khorh** » 16 lis 2006, o 15:23

Undre pisze:nie musi być już widzę rozwiązanie

to podziel się swoją wiedzą tajemną

Bierut · Post autor: **Bierut** » 17 lis 2006, o 00:22

Nie ma rozwiązania w pełni spełniającego warunki zadania. Undre pewnie wymyślił jakąś sztuczkę, która w rzeczywistości nie jest poprawna.

yorgin · Post autor: **yorgin** » 19 lis 2006, o 11:39

Ok znalazłem wreszcie co trzeba by zakończyć ten problem (posłużę się informacjami z książki).
W teorii grafów spotykamy termin: graf Koeniga-graf w ktrórym zbiór wierchołków został przedstawiony jako suma mnogościowa dwóch rozłącznych podzbiorów A i B o tej własności, że kądzy punkt ze zbioru A został połączony z każdym punktem ze zbioru B. ale żadne puntky ze zbioru A (B) nie są pomiędzy sobą połączone. Oznaczmy parę (m,n) jako odpowiednią liczbę elementów zbiorów A i B.
W takim grafie minimalna liczba przecięc wyraża się wzorem:
\(\displaystyle{ p=[\frac{1}{2}m][\frac{1}{2}(m-1)][\frac{1}{2}n][\frac{1}{2}(n-1)]}\)
Dana formuła jest prawdzia dla m,n

Undre · Post autor: **Undre** » 20 lis 2006, o 01:09

Bierut pisze:Nie ma rozwiązania w pełni spełniającego warunki zadania. Undre pewnie wymyślił jakąś sztuczkę, która w rzeczywistości nie jest poprawna.

Ja to widzę tak Oczywiście dla mnie połączenie linią nie oznaczało akurat przejścia przez domek, ale mogę zrobić odpowiednio duże te kwadraty i też będzie ok Jeżeli bierut dla ciebie to jest niepoprawna sztuczka, to już nie mój problem

Bierut · Post autor: **Bierut** » 22 lis 2006, o 00:35

W zadaniu jest napisane, że należy doprowadzić wszystkie linie do domków a ty je okrążyłeś. Żadna linia nie dochodzi do domu.

Undre · Post autor: **Undre** » 22 lis 2006, o 01:46

Widzę, że nie przeczytałeś mojego postu ... powtórzę - mogę zrobić te kwadraty odpowiednio duże ( powiedzmy 4 razy większe ) i będzie OK. Rozumiem iż lubisz dochodzić racji jednak takie czepianie się nie dość, że mija się z celem, to jeszcze psuje karmę. Think about it.