Přeskočit na obsah

Havlův algoritmus

Z Wikipedie, otevřené encyklopedie

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

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ý.

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