Algoritmus Welsh-Powell
Algoritmus Welsh-Powell je grafový algoritmus sloužící k hornímu odhadu chromatického čísla grafu. Jeho vstupem je graf G definovaný jako dvě množiny – uzly V a hrany E. Výstupem je horní odhad chromatického čísla – jeho přesná hodnota je tedy vždy menší nebo rovna vypočítané hodnotě.
Kroky algoritmu
- Inicializuj pracovní seznam S = V a počítadlo i = 1.
- Dokud není seznam S prázdný, opakuj:
- Seřaď uzly v seznamu S do nerostoucí posloupnosti podle jejich stupně.
- Obarvi první uzel v posloupnosti barvou číslo i a stejnou barvu postupně přiřaď i všem dalším uzlům, které s tímto uzlem nesousedí.
- Ze seznamu S odeber všechny právě obarvené uzly.
- Inkrementuj počítadlo i.
Příklad
Inicializace
Na začátku jsou všechny uzly neobarvené (v závorkách jsou uvedeny stupně uzlů). Seznam S je naplněn všemi uzly a seřazen do nerostoucí posloupnosti.
| Seznam S | C(5) | E(4) | F(3) | B(2) | G(2) | A(1) | D(1) |
graf po inicializaci algoritmu
Krok 1
V první iteraci je vybrán první uzel (C) a spolu s dalšími uzly, které s ním nesousedí (G), je obarven barvou číslo 1 (modrá). Poté jsou obarvené uzly odebrány ze seznamu S.
| Seznam S | E(4) | F(3) | B(2) | A(1) | D(1) |
graf po obarvení první barvou
Krok 2
Seznam S není prázdný, algoritmus pokračuje dál. Ve druhé iteraci je opět vybrán první uzel (E) a spolu s dalšími uzly, které s ním nesousedí (A, D), je obarven barvou číslo 2 (žlutá). Poté jsou obarvené uzly odebrány ze seznamu S.
| Seznam S | F(3) | B(2) |
graf po obarvení druhou barvou
Krok 3
Seznam S stále není prázdný, algoritmus pokračuje dál. Ve třetí iteraci je opět vybrán první uzel (F) a spolu s dalšími uzly, které s ním nesousedí (B), je obarven barvou číslo 3 (zelená). Poté jsou obarvené uzly odebrány ze seznamu S.
| Seznam S | (prázdný) |
graf po obarvení třetí a poslední barvou
Krok 4
Seznam S je prázdný, algoritmus končí. Celkem byly použity tři barvy, chromatické číslo grafu je tedy menší nebo rovno třem.
Reference
- Dr. Jeanne Stynes, Computer Science