Grafo nuspalvinimo uždavinys

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 – , kai spalvos priskiriamos briaunoms.

, kurio viršūnės nudažytos trimis spalvomis taip, kad gretimos viršūnės turėtų skirtingas spalvas

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

1. Lewis (2021), pp. 221–246, Chapter 8: Designing sports leages.
2. Lewis (2021), pp. 203–220, Chapter 7: Designing seating plans.
3. Lewis (2021), pp. 247–276, Chapter 9: Designing university timetables.
4. Lewis (2021), pp. 5–6, Section 1.1.3: Scheduling taxis.
5. Lewis (2021), pp. 172–179, Section 6.4: Latin squares and sudoku puzzles.

Literatūra

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

Vikiteka: Grafo spalvinimas – vaizdinė ir garsinė medžiaga