Indeks chromatyczny
Z Wikipedii
Niniejszy artykuł jest częścią cyklu teoria grafów.
 |
|
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
| edytuj ten szablon |
Indeks chromatyczny grafu (χ'(G)) 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.
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ść. V. G. Vizing udowodnił, że 
. Ponieważ oczywiste jest, że 
, więc jeśli znamy stopień grafu wiemy, że indeks chromatyczny przyjmuje jedną z dwóch wartości: 
, 
.
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 . 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.
[edytuj] Zobacz też
| ONZ: Izrael najpierw ewakuował Palestyńczyków, a potem ich ostrzelał |
|
Przynajmniej 30 Palestyńczyków zginęło w Strefie Gazy w ostrzale domu, do którego zostali wcześniej ewakuowani przez izraelskich żołnierzy - wynika z raportu ONZ.
|
| "Nie myślałem, że minister się tak prostytuuje" |
|
Posłanka PiS Grażyna Gęsicka, wzywając rząd do odpowiedzialności za niewykorzystanie funduszy unijnych manipuluje opinią publiczną - ocenił w TVN24 poseł PO Janusz Palikot.
|
| Wypadek na drodze Wrocław-Legnica |
|
Jedna osoba została ranna w wyniku wypadku, do którego doszło w piątek wieczorem niedaleko miejscowości Mazurowice (Dolnośląskie). Droga krajowa nr 94 Wrocław - Legnica została całkowicie zablokowana.
|
| Omar Faris: Niech Izrael opuści nasze ziemie |
|
- Niech Izrael opuści nasze ziemie, a gwarantujemy, że ani jedna rakieta nie spadnie na ich ziemie - mówił przewodniczący Palestyńskiej Koalicji na rzecz Prawa do Powrotu Omar Faris, gość CZATerii w INTERIA.PL.
|
| Juszczenko: Konflikt gazowy był zaplanowany |
|
Ukraina pozwoli rosyjskim obserwatorom na wjazd na jej terytorium w celu nadzorowania tranzytu rosyjskiego gazu do Europy - poinformował prezydent Ukrainy Wiktor Juszczenko po spotkaniu z czeskim premierem Mirkiem Topolankiem w Kijowie.
|