Wikipedia

Indeks chromatyczny: Różnice pomiędzy wersjami

Przeglądaj historię interaktywnie
[wersja nieprzejrzana][wersja nieprzejrzana]
← poprzednia edycjanastępna edycja →
Usunięta treść Dodana treść
WizualnieWikikod
lit.
m rv - pisownia z 'v' jest znacznie bardziej popularniejsza
Linia 5:
Indeks chromatyczny grafu jest równy [[liczba 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ść. WadimV. G. WizingVizing 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. Okazuje się, że znacznie więcej jest grafów o indeksie chromatycznym równym <math>\Delta(G)\,</math>. Grafy takie nazywamy grafami '''klasy 1''', a ich przykładami są [[Graf dwudzielny|grafy dwudzielne]], a także [[Graf pełny|grafy pełne]] o parzystej liczbie wierzchołków. Grafami '''klasy 2''', a więc o indeksie chromatycznym równym <math>\Delta(G)+1\,</math>, są np. nieparzyste [[Cykl (teoria grafów)|cykle]], jak również grafy pełne nieparzystego rzędu.
Źródło: „https://pl.wikipedia.org/wiki/Indeks_chromatyczny”