Farbenie grafu

z Wikipédie, slobodnej encyklopédie
Skočit na navigaci Skočit na vyhledávání

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[upraviť | upraviť kód]

História[upraviť | upraviť kód]

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[upraviť | upraviť kód]

  • 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[upraviť | upraviť kód]