szukanie zaawansowane
 [ Posty: 40 ]  Przejdź na stronę 1, 2, 3  Następna strona
Autor Wiadomość
Mężczyzna Offline
 Tytuł: 3 domki...
PostNapisane: 8 lis 2006, o 18:45 
Użytkownik

Posty: 18
Lokalizacja: znienacka
Nie jestem pewien czy da sie to zadanie rozwiązać :neutral:

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

Obrazek

Obrazek
Góra
Mężczyzna Offline
 Tytuł: 3 domki...
PostNapisane: 8 lis 2006, o 18:57 
Użytkownik
Avatar użytkownika

Posty: 28
Lokalizacja: Toruń
a ta zagadka ma byc w 3D czy 2D ? :)
Góra
Mężczyzna Offline
 Tytuł: 3 domki...
PostNapisane: 8 lis 2006, o 21:18 
Gość Specjalny
Avatar użytkownika

Posty: 2656
Lokalizacja: Wrocław/Sieradz
znając życie 2D :)
Góra
Mężczyzna Offline
 Tytuł: 3 domki...
PostNapisane: 8 lis 2006, o 21:35 
Użytkownik

Posty: 18
Lokalizacja: znienacka
w 3d to by nie bylo problemu :P nie ma tak latwo, mi cos sie zdaje ze to jednak nie do rozwiazania jest, zawsze brakuje jednej linki do domku doprowadzic jednego...
Góra
Mężczyzna Offline
 Tytuł: 3 domki...
PostNapisane: 8 lis 2006, o 23:53 
Użytkownik
Avatar użytkownika

Posty: 202
Lokalizacja: Bytom
Obrazek

cos takiego obleci? :)
Góra
Mężczyzna Offline
 Tytuł: 3 domki...
PostNapisane: 9 lis 2006, o 08:13 
Użytkownik

Posty: 18
Lokalizacja: znienacka
nie, bo wyprowadziles linie z domkow...

probowalem sam nawet przestawiać te punkty i też zawsze brakuje dla 1 żyły miejsca...
Góra
Mężczyzna Offline
 Tytuł: 3 domki...
PostNapisane: 11 lis 2006, o 16:16 
Administrator
Avatar użytkownika

Posty: 12708
Lokalizacja: Kraków
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ć. :D

Ma niewiedza i brak odpowiedniej ksiązki sprawia ze nie opieram sie na konkretach tylko na tym co pamietam.
Góra
Mężczyzna Offline
 Tytuł: 3 domki...
PostNapisane: 15 lis 2006, o 20:46 
Użytkownik

Posty: 11
Lokalizacja: Szczucin
minimalnie musi być jedno przecięcie
Góra
Mężczyzna Offline
 Tytuł: 3 domki...
PostNapisane: 15 lis 2006, o 23:29 
Gość Specjalny
Avatar użytkownika

Posty: 1430
Lokalizacja:
nie musi być :P już widzę rozwiązanie :D
Góra
Mężczyzna Offline
 Tytuł: 3 domki...
PostNapisane: 16 lis 2006, o 15:23 
Użytkownik

Posty: 18
Lokalizacja: znienacka
Undre napisał(a):
nie musi być :P już widzę rozwiązanie :D

to podziel się swoją wiedzą tajemną :twisted:
Góra
Mężczyzna Offline
 Tytuł: 3 domki...
PostNapisane: 17 lis 2006, o 00:22 
Użytkownik
Avatar użytkownika

Posty: 639
Lokalizacja: Wrocław
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.
Góra
Mężczyzna Offline
 Tytuł: 3 domki...
PostNapisane: 19 lis 2006, o 11:39 
Administrator
Avatar użytkownika

Posty: 12708
Lokalizacja: Kraków
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:
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<7
Tak więc, zgodnie z powyższym wzorem, minimalna liczba przecięc grafu (3,3) wynosi 1, co rozwiewa wszelkie wątpliwości co do postawionego w temacie problemu.
Góra
Mężczyzna Offline
 Tytuł: 3 domki...
PostNapisane: 20 lis 2006, o 01:09 
Gość Specjalny
Avatar użytkownika

Posty: 1430
Lokalizacja:
Bierut napisał(a):
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.


Obrazek

Ja to widzę tak :P 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 :P Jeżeli bierut dla ciebie to jest niepoprawna sztuczka, to już nie mój problem :P
Góra
Mężczyzna Offline
 Tytuł: 3 domki...
PostNapisane: 22 lis 2006, o 00:35 
Użytkownik
Avatar użytkownika

Posty: 639
Lokalizacja: Wrocław
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.
Góra
Mężczyzna Offline
 Tytuł: 3 domki...
PostNapisane: 22 lis 2006, o 01:46 
Gość Specjalny
Avatar użytkownika

Posty: 1430
Lokalizacja:
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.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 40 ]  Przejdź na stronę 1, 2, 3  Następna strona


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Trzy domki i media  czardasz  4
 krasnolódki - domki  Flamaster90  2
 Trzej Panowie i trzy domki  MrRipley  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl