Wersja z 22:50, 13 kwi 2006 edytuj Kuszi (dyskusja \| edycje) Redaktorzy 4660 edycji m redakcja ← poprzednia edycja		Wersja z 15:05, 25 maj 2006 edytuj anuluj edycję A. (dyskusja \| edycje) Redaktorzy 17 157 edycji m dr. następna edycja →
Linia 1: '''Indeks chromatyczny''' [[Graf (matematyka)\|grafu]] (<math>\chi'(G)</math>) jest pojęciem związanym z [[kolorowanie krawędzi\|kolorowaniem krawędzi]] grafu. Określa minimalną liczbę kolorów wystarczającą do prawidłowego [[kolorowanie krawędzi\|pokolorowania krawędzi]] grafu. Indeks chromatyczny grafu jest równy [[~~Kolorowanie~~liczba ~~grafu~~chromatyczna\|liczbie chromatycznej]] jego [[graf krawędziowy\|grafu krawędziowego]]. Znalezienie indeksu chromatycznego jest problemem [[Problem NP -trudny\|NP -trudnym]], mimo że można bardzo dokładnie oszacować jego wartość. [[V. G. Vizing]] udowodnił, że <math>\chi'(G)\leq \Delta(G)+1</math>. Ponieważ oczywiste jest, że <math>\chi'(G)\geq \Delta(G)</math>, więc jeśli znamy [[stopień grafu]] wiemy, że indeks chromatyczny przyjmuje jedną z dwóch wartości: <math> \Delta(G)</math>, <math> \Delta(G)+1 </math>. Stało się to pretekstem do podziału wszystkich grafów na dwie klasy ze względu na indeks chromatyczny. Okazauje się, że znacznie więcej jest grafów o indeksie chromatycznym równym <math> \Delta(G)</math>. ===Zobacz też: === [[kolorowanie krawędzi]], [[~~Kolorowanie grafu\|~~liczba chromatyczna]], *[[graf krawędziowy]] [[Kategoria:Teoria grafów]] [[en:Edge coloring]]

Indeks chromatyczny: Różnice pomiędzy wersjami