szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 3 lip 2015, o 11:21 
Użytkownik

Posty: 37
Lokalizacja: Leszno
Powiedzmy, że mamy taki najprostszy graf dwudzielny
https://pl.wikipedia.org/wiki/Twierdzen ... h_K3,3.svg

"W grafie dwudzielnym każdy cykl ma parzystą długość."

Na powyższym obrazku łatwo jest zliczyć, że powyższe stwierdzenie jest prawdziwe. Tylko jak tego matematycznie dowieść ?
Góra
Mężczyzna Offline
PostNapisane: 3 lip 2015, o 11:24 
Użytkownik

Posty: 394
Lokalizacja: Warszawa
O to ,czy jest to najprostszy graf dwudzielny bym się spierał (zauważ ,że to graf dwudzielny pełny). Podpowiedź: jakbyś miał mi napisać co to jest graf dwudzielny to co byś nasmarował?
Góra
Mężczyzna Offline
PostNapisane: 3 lip 2015, o 11:53 
Użytkownik

Posty: 37
Lokalizacja: Leszno
Swoimi słowami to taki graf, który ma dwa różne zbiory wierzchołków i każdy z tych wierzchołków łączy się z każdym wierzchołkiem z drugiego zbioru, nie łącząc się przy tym z wierzchołkiem ze swojego zbioru.
Góra
Mężczyzna Offline
PostNapisane: 3 lip 2015, o 12:03 
Użytkownik

Posty: 394
Lokalizacja: Warszawa
No właśnie,a w cyklu musimy wrócić do wierzchołka początkowego. Da się to zrobić przechodząc nieparzystą ilość razy? No nie,nie da się. Najprościej to napisać tak: graf dwudzieln można podzielić na dwie klasy dwudzielności V_{1} i V_{2} Startujemy więc z cyklem:
v_{0}  \in  V_{1}, v_{1} \in  V_{2},...........,v_{n} \in V_{2}, v_{0} \in V_{1} Już widzisz? Jaki wnioski można wyciagnąć?
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 automorfizmy w grafie  gabriela86  2
 Ile krawedzi w grafie K50,51,150 ma jego drzewo rozpinajace  piczer08  3
 Ścieżka P5 w grafie  pozone  1
 obliczanie sumy, wykazanie sumy oraz cykle  fiman  1
 Dowód na istnienie cyklu Hamiltona w grafie kostki  luki1423  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl