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 editovat

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   neboli pro vrchol   vyber co nejmenší číslo barvy po odebrání čísel barev všech již obarvených sousedů tohoto vrcholu.

Počet použitých barev editovat

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