Grafo spalvinimas

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką
Peterseno grafas, kurio viršūnės nudažytos trimis spalvomis taip, kad gretimos viršūnės turėtų skirtingas spalvas

Grafo spalvinimas arba grafo dažymas - grupė grafų teorija uždavinių, kuriuose siekiama grafo elementams priskirti spalvas taip, kad būtų tenkinamos tam tikros sąlygos (paprastai - kad gretimi grafo elementai turėtų skirtingas spalvas). Iš tokių uždavinių dažniausiai naudojamas viršūnių spalvinimas, kai kiekvienai viršūnei priskiriama spalva taip, kad gretimos viršūnės turėtų skirtingas spalvas, kiek rečiau - briaunų spalvinimas, kai spalvos priskiriamos briaunoms.


Commons-logo.svg Vikiteka: Grafo spalvinimas – vaizdinė ir garsinė medžiaga

Vikiteka