Grafo spalvinimas
(Nukreipta iš puslapio Grafo nuspalvinimo uždavinys)
|
Šiam straipsniui ar jo daliai trūksta išnašų į šaltinius. Jūs galite padėti Vikipedijai pridėdami tinkamas išnašas su šaltiniais. |
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.
Peterseno grafas, kurio viršūnės nudažytos trimis spalvomis taip, kad gretimos viršūnės turėtų skirtingas spalvas
|
Šis su matematika susijęs straipsnis yra nebaigtas. Jūs galite prisidėti prie Vikipedijos papildydami šį straipsnį. |