Mohó színezés | mateking

A mohó színezés egy algoritmus a gráfok színezésére.

Lényege, hogy sorba rakjuk a gráf csúcsait, és elkezdjük színezni úgy, hogy minden csúcs színezéséhez a lehető legkisebb sorszámú színt használjuk. Ezt addig folytatjuk, amíg az összes csúcs ki nem lesz színezve, és így elhasználunk legfeljebb $\Delta(G)+1$ darab színt.

Megnézem az erről a képletről szóló tananyagot

Ezt a képletet még az alábbi kurzusainkban is megtalálod:

Diszkrét matematika / Kromatikus szám, klikk, perfekt gráfok / Mohó színezés, becslés a kromatikus számra

Bevezetés a számításelméletbe 2 / Kromatikus szám, klikk, perfekt gráfok / Mohó színezés, becslés a kromatikus számra

Számítástudomány alapjai / Kromatikus szám, klikk, perfekt gráfok / A mohó színezés, becslés a kromatikus számra

Számítástudomány / Kromatikus szám, klikk, perfekt gráfok / A mohó színezés, becslés a kromatikus számra

A mohó színezés egy algoritmus a gráfok színezésére.