Indeks chromatyczny

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
Niniejszy artykuł jest częścią cyklu teoria grafów.




Najważniejsze pojęcia
graf
drzewo
podgraf
cykl
klika
stopień wierzchołka
stopień grafu
dopełnienie grafu
obwód grafu
pokrycie wierzchołkowe
liczba chromatyczna
indeks chromatyczny
izomorfizm grafów
homeomorfizm grafów


Wybrane klasy grafów
graf pełny
graf spójny
drzewo
graf dwudzielny
graf regularny
graf eulerowski
graf hamiltonowski
graf planarny


Algorytmy grafowe
A*
Bellmana-Forda
Dijkstry
Fleury'ego
Floyda-Warshalla
Johnsona
Kruskala
Prima
przeszukiwanie grafu
wszerz
w głąb
najbliższego sąsiada


Zagadnienia przedstawiane jako problemy grafowe
problem komiwojażera
problem chińskiego listonosza
problem marszrutyzacji
problem kojarzenia małżeństw


Inne zagadnienia
kod Graya
diagram Hassego
kod Prüfera


Indeks chromatyczny grafu () jest pojęciem związanym z kolorowaniem krawędzi grafu. Określa minimalną liczbę kolorów wystarczającą do prawidłowego pokolorowania krawędzi grafu. Innymi słowy, to najmniejsza liczba kolorów potrzebnych do pomalowania krawędzi tak, aby żadne dwie krawędzie mające wspólny wierzchołek nie były tego samego koloru[1][2].

Indeks chromatyczny grafu jest równy liczbie chromatycznej jego grafu krawędziowego.

Znalezienie indeksu chromatycznego jest problemem NP-trudnym, mimo że można bardzo dokładnie oszacować jego wartość. Wadim G. Wizing udowodnił, że . Ponieważ , więc jeśli znamy stopień grafu wiemy, że indeks chromatyczny przyjmuje jedną z dwóch wartości: , .

Konsekwencją twierdzenia Wizinga jest podział wszystkich grafów na dwie klasy ze względu na indeks chromatyczny. Okazuje się, że znacznie więcej jest grafów o indeksie chromatycznym równym . Grafy takie nazywamy grafami klasy 1, a ich przykładami są grafy dwudzielne, a także grafy pełne o parzystej liczbie wierzchołków. Grafami klasy 2, a więc o indeksie chromatycznym równym , są np. nieparzyste cykle, jak również grafy pełne nieparzystego rzędu[3].

Indeks chromatyczny dowolnego nieparzystego cyklu wynosi 3

Zobacz też[edytuj | edytuj kod]

Przypisy[edytuj | edytuj kod]

  1. http://informatyka.umcs.lublin.pl/files/krajka.pdf
  2. Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 96. ISBN 0-387-95014-1.
  3. Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 103-104. ISBN 0-387-95014-1.