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ść ?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
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 
 Najkrótsza droga w grafie  wojciech007  1
 znaleźć w grafie węzeł przez który nie przechodzą ścieżki  johnyjj2  0
 liczba cykli długości 4 w grafie G  JakubCh  0
 Ilość krawędzi w grafie  mCichy13  4
 Wykazać, że w grafie Petersena istnieje droga Hamiltona  stonek89  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl