Grafo spalvinimas

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.

Taikymas

Grafo spalvinimo uždavinys iškyla daugelyje praktinių sričių, tokių kaip sporto tvarkaraščio sudarymas, sėdimų vietų planų kūrimas, egzaminų ir taksi tvarkaraščių kūrimas bei Sudoku galvosūkių sprendimas.

Literatūra

• Lewis, R. M. R. (2021), Guide to Graph Colouring, Texts in Computer Science, doi:10.1007/978-3-030-81054-2, ISBN 978-3-030-81053-5