Farbenie grafu

Farbenie grafu je špeciálny prípad označovania grafu, na základe tradície sa tieto značky nazývajú farby.

Základné druhy farbenia grafu
farbenie vrcholov grafu
farbenie hrán grafu
farbenie plôch grafu v planárnych grafoch

História
Prvé výsledky farbenia grafov sa týkali farbenia máp. Francis Guthrie postuloval teorému štyroch farieb, ktorá vraví, že každú mapu možno vyfarbiť pomocou štyroch farieb tak, že susediace plochy budú mať rôzne farby. Táto teoréma dlho odolávala dôkazu, bola dokázaná až v roku 1976.

 Aplikácie 
 priradenie registrov počítača
 priradenie rádiových frekvencií
 problém nákupných tašiek
 rozvrhovanie voliteľných predmetov
 minimalizácia počtu autobusových stanovíšť
 fázovanie svetelne riadenej križovatky

 Zdroje 
http://frcatel.fri.uniza.sk/users/paluch/grkap8-nopics.pdf
Kategória:Teória grafov