Havlův algoritmus

algoritmus z teorie grafů

Havlův algoritmus (v zahraniční literatuře též Havel-Hakimi algoritmus) je algoritmus řešící jeden z problémů teorie grafů, totiž ověření, jestli pro konečný soubor nezáporných čísel existuje graf, pro který platí, že soubor stupňů jeho uzlů je permutace zadaného seznamu. Pokud takový graf existuje, nazveme soubor čísel kreslitelným a tento rekurzivní algoritmus ho dokáže najít a sestrojit. V opačném případě nám dává důkaz toho, že takový graf nemůže existovat. Algoritmus byl poprvé zveřejněn v roce 1955 českým matematikem Václavem Havlem.[1] V roce 1962 stejný algoritmus zveřejnil i Hakimi.[2]

Algoritmus

editovat

Algoritmus vychází z následující věty:

Nechť   je konečný nerostoucí soubor nezáporných celých čísel a  . Potom soubor   nazveme kreslitelným právě tehdy, když konečný soubor čísel   je kreslitelný a obsahuje pouze nezáporná čísla.

Pokud chceme dokázat, že je soubor   kreslitelný, použijeme maximálně   krát předchozí větu. Jelikož se může stát, že soubor   nebude nerostoucí, je potřeba soubor   před dalším použitím předchozí věty nejdříve seřadit.

Algoritmus končí ve chvíli, kdy soubor   v nějakém kroku obsahuje samé nuly.

Konstrukce grafu pomocí Havlova algoritmu probíhá tak, že v každém kroku algoritmu přidáme mezi uzly   nové hrany. Konkrétně pokud je možné transformovat soubor   na  , pak do grafu přidáme hrany  . Tím v grafu budeme mít všechny požadované hrany pro vrchol   a v dalším kroku tak pracujeme již jen s o 1 menším počtem vrcholů.

Jestliže v libovolném kroku není možné   transformovat na  , pak věta dokazuje, že původní soubor   není kreslitelný.

Reference

editovat
  1. HAVEL, Václav. Poznámka o existenci konečných grafů. Časopis pro pěstování matematiky. 1955, roč. 080, čís. 4, s. 477–480. Dostupné online [cit. 2017-04-27]. ISSN 0528-2195. 
  2. HAKIMI, S. L. On realizability of a set of integers as degrees of the vertices of a linear graph. S. 496–506. Journal of the Society for Industrial and Applied Mathematics [online]. 1962 [cit. 2017-04-27]. Čís. 10, s. 496–506. Dostupné online. (anglicky) 

Související články

editovat