Indeks chromatyczny

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Heniek1991
Użytkownik
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

Post autor: Heniek1991 »

Nie mam pomysłu jak pokazać, że kubiczny(3-regularny) graf hamiltonowski ma indeks chromatyczny równy 3.
Użytkownik
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

Post autor: »

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.
Heniek1991
Użytkownik
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

Post autor: Heniek1991 »

Ok, dzięki. Ale u mnie graf hamiltonowski miał cykl hamiltona, a graf półhamiltonowski miał drogę hamiltona
Użytkownik
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

Post autor: »

W takim razie jest jeszcze prościej, bo końcówka argumentu jest o połowę krótsza.

Q.
ODPOWIEDZ