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 {.barva} \ |\ j<i\land 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ě $\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$. 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.