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.
1-faktoryzacja grafu
-
Mruczek
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
1-faktoryzacja grafu
\(\displaystyle{ 1}\)-faktoryzacja to rozłożenie krawędzi grafu na doskonałe skojarzenia.
Spostrzeżenie:
Graf \(\displaystyle{ 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 (\(\displaystyle{ 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 \(\displaystyle{ 3}\), to po jego usunięciu stopień każdego wierzchołka będzie wynosił \(\displaystyle{ 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 \(\displaystyle{ 1}\)-faktoryzację grafu, sprzeczność, cnd.
Spostrzeżenie:
Graf \(\displaystyle{ 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 (\(\displaystyle{ 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 \(\displaystyle{ 3}\), to po jego usunięciu stopień każdego wierzchołka będzie wynosił \(\displaystyle{ 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 \(\displaystyle{ 1}\)-faktoryzację grafu, sprzeczność, cnd.