First fit algoritmus barvení grafu

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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 | editovat zdroj]

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 | editovat zdroj]

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.