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

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

Tento článok týkajúci sa matematiky je zatiaľ „výhonok“. Pomôž Wikipédii tým, že ho doplníš a rozšíriš.

Zdroje

http://frcatel.fri.uniza.sk/users/paluch/grkap8-nopics.pdf

Zdroj:
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.