Grafo spalvinimas

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Jump to navigation Jump to search
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