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.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 19 kwi 2017, o 23:10 
Użytkownik

Posty: 1076
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 
 Drzewa spinające grafu połączonego krawędzią z cyklem  iks2011  0
 Liczba chromatyczna i dopełnienie grafu  gardner  5
 Liczb chromatyczna grafu, a zbiór niezależny  mqtqbenc  1
 Izomorfizm grafu  darksaq  1
 Udowodnij, że krawędzie dowolnego grafu nieskierowanego  matinf  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl