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 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 ${\displaystyle \min(\mathbb {Z} ^{+}\setminus \{\mathrm {v} _{j}\mathrm {.barva} \ |\ j<i\land v_{j}\in N(v_{i})\})}$ neboli pro vrchol ${\displaystyle v}$ vyber co nejmenší číslo barvy po odebrání čísel barev všech již obarvených sousedů tohoto vrcholu.

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