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{.}\mathrm{b}\mathrm{a}\mathrm{r}\mathrm{v}\mathrm{a}|j<i\wedge v_j\in N(v_i)\})$ 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ě $\mathrm{△}(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ě $\mathrm{△}(G)$ sousedů. Vybereme-li jeden vrchol, který má počet sousedů právě $\mathrm{△}(G)$ a budeme-li uvažovat nejhorší případ, totiž že každý ze sousedů má jinou barvu z množiny $\{1,\dots ,\mathrm{△}(G)\}$, budeme muset na tento vybraný vrchol použít barvu $\mathrm{△}(G)+1$. V tuto chvíli máme k dispozici barvy $\{1,2,\dots ,\mathrm{△}(G),\mathrm{△}(G)+1\}$ a víme, že v grafu neexistuje vrchol, který by měl více než $\mathrm{△}(G)$ sousedů. Vždy tedy bude možné k obarvení použít jednu z barev $\{1,\dots ,\mathrm{△}(G)+1\}$ a další nebude nikdy třeba přidávat. Šablona:Autoritní data