First fit algoritmus barvení grafu

First fit je algoritmus z teorie grafů. Je schopný najít obarvení libovolného grafu, není ale zaručeno, že půjde o obarvení minimální, tedy používající minimální potřebný počet různých barev. Jedná se o tzv. hladový algoritmus.

Algoritmus

Algoritmus postupně prochází všechny vrcholy grafu a snaží se jim přiřazovat barvu o co nejmenším čísle na základě barev jejich sousedů.

pocet_barev := 0 PRO i := 0 DO n OPAKUJ: volna_barva := najdi_nejmensi_volnou_barvu( i, G ) v_i.barva := volna_barva POKUD volna_barva > pocet_barev: pocet_barev := pocet_barev + 1

Přičemž funkce najdi_nejmensi_volnou_barvu vrací nejmenší číslo barvy, které není použito u žádného ze sousedních vrcholů. Matematicky bychom chování této funkce mohli popsat jako \min( \mathbb{Z}^+ \setminus \{ \mathrm{v}_j\mathrm{. +morebarva}\ |\ j neboli pro vrchol v vyber co nejmenší číslo barvy po odebrání čísel barev všech již obarvených sousedů tohoto vrcholu.

Počet použitých barev

Tento algoritmus použije k obarvení maximálně \triangle(G) + 1 barev neboli o jedna více než je maximální stupeň vrcholu v grafu.

Pro každý vrchol nějakého grafu totiž platí, že má maximálně \triangle(G) sousedů. Vybereme-li jeden vrchol, který má počet sousedů právě \triangle(G) a budeme-li uvažovat nejhorší případ, totiž že každý ze sousedů má jinou barvu z množiny \{1,\ldots,\triangle(G)\}, budeme muset na tento vybraný vrchol použít barvu \triangle(G) + 1. +more V tuto chvíli máme k dispozici barvy \{1,2,\ldots,\triangle(G),\triangle(G) + 1\} a víme, že v grafu neexistuje vrchol, který by měl více než \triangle(G) sousedů. Vždy tedy bude možné k obarvení použít jednu z barev \{1,\ldots,\triangle(G) + 1\} a další nebude nikdy třeba přidávat.

Kategorie:Algoritmy Kategorie:Teorie grafů Kategorie:Grafové algoritmy