Pereiti prie turinio

Grafo spalvinimas

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
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[redaguoti | redaguoti vikitekstą]

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 | redaguoti vikitekstą]

  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[redaguoti | redaguoti vikitekstą]