Indeks chromatyczny
-
- Użytkownik
- Posty: 111
- Rejestracja: 14 paź 2010, o 16:58
- Płeć: Mężczyzna
- Lokalizacja: Lublin / Warszawa
- Podziękował: 1 raz
- Pomógł: 1 raz
Indeks chromatyczny
Nie mam pomysłu jak pokazać, że kubiczny(3-regularny) graf hamiltonowski ma indeks chromatyczny równy 3.
-
- 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
Indeks chromatyczny
Z lematu o uściskach dłoni wynika, że taki graf ma parzystą liczbę wierzchołków. W takim razie rozważmy istniejącą drogę Hamiltona i pomalujmy ją na biało-czarno (w ten sposób pierwsza i ostatnia krawędź w tej drodze będzie biała). Usuńmy to co już pomalowane. Pierwszy i ostatni wierzchołek są teraz stopnia dwa, a pozostałe stopnia jeden. Jeśli dwa wyróżnione wierzchołki są połączone (czyli jeśli istnieje cykl Hamiltona), to malujemy łączącą je krawędź na czarno, a całą resztę na czerwono. Jeśli nie są połączone, to malujemy dwie krawędzie wychodzące z pierwszego wierzchołka na czarno i czerwono, i tak samo z ostatniego wierzchołka, a resztę na czerwono. W każdym przypadku wystarczyły nam trzy kolory.
Q.
Q.
-
- Użytkownik
- Posty: 111
- Rejestracja: 14 paź 2010, o 16:58
- Płeć: Mężczyzna
- Lokalizacja: Lublin / Warszawa
- Podziękował: 1 raz
- Pomógł: 1 raz
Indeks chromatyczny
Ok, dzięki. Ale u mnie graf hamiltonowski miał cykl hamiltona, a graf półhamiltonowski miał drogę hamiltona