Viršūnių spalvinimas

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

 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 .

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

 Šaltiniai 

Kategorija:Grafų teorija