szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 19 kwi 2017, o 21:24 
Użytkownik

Posty: 22
Lokalizacja: Poznań
Graf prosty G jest 3-regularny. Pokaż, że graf który nie ma 1-faktoryzacji nie jest grafem Hamiltona.

Z góry bardzo dziękuję, jeśli ktoś mi pomoże.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna Offline
PostNapisane: 19 kwi 2017, o 22:10 
Użytkownik

Posty: 1093
1-faktoryzacja to rozłożenie krawędzi grafu na doskonałe skojarzenia.

Spostrzeżenie:
Graf 3-regularny musi mieć parzystą liczbę wierzchołków - gdyby miał nieparzystą to suma stopni byłaby nieparzysta - sprzeczność.

Dowód nie wprost.
Zał, że ten graf ma cykl Hamiltona. Ten cykl ma parzystą długość. Dlatego biorąc co drugą krawędź z tego cyklu dostajemy skojarzenie doskonałe (1-faktor). To znaczy, że cykl Hamiltona rozpada się na dwa skojarzenia doskonałe.
Usuńmy z tego grafu ten cykl Hamiltona. Ponieważ stopień każdego wierzchołka wynosi 3, to po jego usunięciu stopień każdego wierzchołka będzie wynosił 1 - to co pozostanie będzie doskonałym skojarzeniem.
W ten sposób rozłożyliśmy graf na trzy doskonałe skojarzenia, czyli otrzymaliśmy 1-faktoryzację grafu, sprzeczność, cnd.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Skojarzenie doskonałe grafu dwudzielnego  Szemek  6
 Dowód na nie istnienie danego grafu  tomek1172  1
 Kolorowanie grafu - artykuł  wiedzmac  4
 Wyznaczanie grafu z wielomianu chromatycznego  paulina223  1
 Spójność grafu regularnego  Anonymous  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl