szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 19 kwi 2017, o 22: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 23:10 
Użytkownik

Posty: 1087
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 
 Średnica grafu niespójego i spójnego  matinf  10
 Kolorowanie grafu  rubenz  0
 Grafy - drzewa opinające względem drugiego grafu  Rikka  1
 Problem max kliki dla dopełnienia grafu.  Avicularia  0
 Kolorowanie grafu - zadanie 3  norbert22  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl