Grafo spalvinimas

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.

 Šaltiniai 

 Literatūra 


Kategorija:Grafų teorija