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 – , 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

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, ISBN 978-3-030-81053-5 

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