Jak udowodnić:
Jeśli graf nie zawiera cykli nieparzystych to jest dwudzielny?
Grafy cykle nieparzyste
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Grafy cykle nieparzyste
Indukcyjnie ze względu na liczbę wierzchołków.
Weźmy dowolny graf o \(\displaystyle{ n}\) wierzchołkach. Usuńmy dowolny wierzchołek \(\displaystyle{ w}\), a resztę wierzchołków pomalujmy na biało i czarno (można to zrobić z założenia indukcyjnego). Niech graf po usunięciu naszego wierzchołka składa się ze spójnych składowych \(\displaystyle{ G_1,G_2,\ldots , G_k}\). Dołączmy teraz z powrotem usunięty wierzchołek. Gdyby ten wierzchołek był połączony z wierzchołkami czarnym i białym należącymi do pewnego \(\displaystyle{ G_i}\), to mielibyśmy cykl o nieparzystej długości (dlaczego?), czyli sprzeczność. Tak więc dla każdego \(\displaystyle{ i}\) wierzchołek \(\displaystyle{ w}\) jest połączony tylko z czarnymi wierzchołkami \(\displaystyle{ G_i}\) albo tylko z białymi wierzchołkami \(\displaystyle{ G_i}\). Jeśli tylko z czarnymi, to w takim \(\displaystyle{ G_i}\) przemalujmy wierzchołki odwrotnie (czarne na biało, a białe na czarno). Teraz już \(\displaystyle{ w}\) połączony jest tylko z białymi wierzchołkami, a zatem można go pomalować na czarno, co kończy dowód.
Q.
Weźmy dowolny graf o \(\displaystyle{ n}\) wierzchołkach. Usuńmy dowolny wierzchołek \(\displaystyle{ w}\), a resztę wierzchołków pomalujmy na biało i czarno (można to zrobić z założenia indukcyjnego). Niech graf po usunięciu naszego wierzchołka składa się ze spójnych składowych \(\displaystyle{ G_1,G_2,\ldots , G_k}\). Dołączmy teraz z powrotem usunięty wierzchołek. Gdyby ten wierzchołek był połączony z wierzchołkami czarnym i białym należącymi do pewnego \(\displaystyle{ G_i}\), to mielibyśmy cykl o nieparzystej długości (dlaczego?), czyli sprzeczność. Tak więc dla każdego \(\displaystyle{ i}\) wierzchołek \(\displaystyle{ w}\) jest połączony tylko z czarnymi wierzchołkami \(\displaystyle{ G_i}\) albo tylko z białymi wierzchołkami \(\displaystyle{ G_i}\). Jeśli tylko z czarnymi, to w takim \(\displaystyle{ G_i}\) przemalujmy wierzchołki odwrotnie (czarne na biało, a białe na czarno). Teraz już \(\displaystyle{ w}\) połączony jest tylko z białymi wierzchołkami, a zatem można go pomalować na czarno, co kończy dowód.
Q.
-
King James
- Użytkownik
- Posty: 150
- Rejestracja: 19 kwie 2007, o 22:52
- Płeć: Mężczyzna
- Lokalizacja: Biłgoraj/Kraków
- Pomógł: 39 razy
Grafy cykle nieparzyste
Alternatywne podejście. Możemy się ograniczyć do jednej spójnej składowej. Rozważmy drzewo rozpinające DFS grafu \(\displaystyle{ G}\) ukorzenione w wierzchołku \(\displaystyle{ v}\). Przypiszmy każdemu wierzchołkowi jego głębokość w drzewie modulo \(\displaystyle{ 2}\). Tak otrzymane kolorowanie jest poprawne, gdyż w przeciwnym razie gdyby dwa wierzchołki \(\displaystyle{ w,u}\) tego samego koloru były połączone krawędzią, to byłaby to krawędź niedrzewowa, dokładając do niej \(\displaystyle{ w}\)-\(\displaystyle{ u}\) ścieżkę w drzewie, znaleźlibyśmy cykl nieparzystej długości, sprzeczność.