Viršūnių spalvinimas

Viršūnių spalvinimas (angl. vertex coloring) - grafo spalvinimo variantas, kai grafo viršūnėms priskiriamos spalvos taip, kad gretimos viršūnės turėtų skirtingas spalvas.^[1]

Peterseno grafas, kurio viršūnės nudažytos trimis spalvomis

Chromatinis skaičius

Mažiausias skaičius spalvų, kuriomis galima nudažyti grafo viršūnes, vadinamas grafo chromatiniu skaičiumi.

Esama įvairių grafo chromatinio skaičiaus įverčių. Pavyzdžiui, keturių spalvų teorema teigia, kad plokščiojo grafo chromatinis skaičius neviršija keturių.

Algoritmai

Bendru atveju patikrinti, ar n viršūnių turintis grafas gali būti nudažytas k spalvų galima peržiūrint visus derinius iš n elementų po k (kiekvienai viršūnei priskiriama viena iš k spalvų). Ieškant chromatinio skaičiaus tokius patikrinimus reikia atlikti k reikšmėms nuo 1 iki n, tad algoritmo laikinis sudėtingumas yra ${\displaystyle O((n+1)!)}$.

Kadangi tikslus algoritmas yra lėtas, paprastai naudojami euristiniai algoritmai.

Šaltiniai

1. „Vertex Coloring -- from Wolfram MathWorld“. mathworld.wolfram.com. Nuoroda tikrinta 2024-02-02.