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 redaguoti
Grafo spalvinimo uždavinys iškyla daugelyje praktinių sričių, tokių kaip sporto tvarkaraščio sudarymas,[1] sėdimų vietų planų kūrimas,[2] egzaminų[3] ir taksi tvarkaraščių kūrimas[4] bei Sudoku galvosūkių sprendimas.[5]
Šaltiniai redaguoti
- ↑ Lewis (2021), pp. 221–246, Chapter 8: Designing sports leages.
- ↑ Lewis (2021), pp. 203–220, Chapter 7: Designing seating plans.
- ↑ Lewis (2021), pp. 247–276, Chapter 9: Designing university timetables.
- ↑ Lewis (2021), pp. 5–6, Section 1.1.3: Scheduling taxis.
- ↑ Lewis (2021), pp. 172–179, Section 6.4: Latin squares and sudoku puzzles.
Literatūra redaguoti
- Lewis, R. M. R. (2021), Guide to Graph Colouring, Texts in Computer Science, doi:, ISBN 978-3-030-81053-5
|
Šis su matematika susijęs straipsnis yra nebaigtas. Jūs galite prisidėti prie Vikipedijos papildydami šį straipsnį. |