UKTG Prednáška 12

Zhrnutie prednášky

Prednáška sa venuje farbeniu grafov. Zavádza vrcholové a hranové k-farbenie, regulárne farbenie so susednými objektmi rôznej farby, chromatické číslo χ(G) a chromatický index χ'(G). Greedy algoritmus dáva horný odhad χ(G) ≤ Δ(G) + 1. Odhad je tesný pre kompletné grafy a nepárne kružnice, zatiaľ čo bipartitné grafy majú χ ≤ 2 pri ľubovoľne veľkom maximálnom stupni. Brooksova veta (1941) tvrdí, že pre ostatné grafy stačí Δ(G) farieb. Na záver prednáška začína farbenie rovinných grafov a historický pôvod problému štyroch farieb, ktorý si všimol Francis Guthrie pri farbení politických máp.

• - Vrcholové k-farbenie je zobrazenie vrcholov do množiny {1,…,k}; regulárne farbenie priraďuje susedným objektom rôzne farby.
• - Chromatické číslo χ(G) je najmenšie k, pre ktoré existuje regulárne vrcholové k-farbenie; chromatický index χ'(G) je analogický parameter pre hrany.
• - Greedy farbenie vrcholov v ľubovoľnom poradí dáva odhad χ(G) ≤ Δ(G) + 1.
• - Odhad je tesný pre kompletné grafy K_n (χ = n, Δ = n−1) a nepárne kružnice (χ = 3, Δ = 2).
• - Medzera medzi χ(G) a Δ(G) môže byť ľubovoľne veľká, napríklad pri bipartitných grafoch, ktoré majú χ ≤ 2.
• - Brooksova veta (1941): ak G nie je kompletný graf ani nepárna kružnica, tak χ(G) ≤ Δ(G).
• - Farbenie rovinných grafov vzniklo z Guthrieho pozorovania o farbení politických máp v polovici 19. storočia.

Zhrnutie pripravené s pomocou AI z prepisu videa.