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

Posty: 26
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.
Góra
Mężczyzna Offline
PostNapisane: 19 kwi 2017, o 22:10 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
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 
 Dwa różne wierzchołki grafu o tym samym stopniu  rajban  2
 kolorowanie grafu co ru nie gra?  anna_y  2
 Spójność grafu  Arst  0
 Kwadrat grafu - zadanie 2  gorgonek  0
 Liczba chromatyczna grafu.  Fengson  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl