Havlův algoritmus

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. V roce 1962 stejný algoritmus zveřejnil i Hakimi.

Algoritmus

Algoritmus vychází z následující věty:Nechť S = (d_1,\ldots,d_n) je konečný nerostoucí soubor nezáporných celých čísel a n > 1. Potom soubor S nazveme kreslitelným právě tehdy, když konečný soubor čísel S' = ( d_2 - 1, d_3 -1, \ldots, d_{d_1+1}-1, d_{d_1+2}, \ldots, d_n ) je kreslitelný a obsahuje pouze nezáporná čísla. +morePokud chceme dokázat, že je soubor S kreslitelný, použijeme maximálně n-1 krát předchozí větu. Jelikož se může stát, že soubor S' nebude nerostoucí, je potřeba soubor S' před dalším použitím předchozí věty nejdříve seřadit.

Algoritmus končí ve chvíli, kdy soubor S' 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 v_1,\ldots,v_n nové hrany. Konkrétně pokud je možné transformovat soubor S na S', pak do grafu přidáme hrany \{v_1, v_2\}, \{v_1, v_3\}, \ldots, \{v_1,v_{d_1+1}\}. +more Tím v grafu budeme mít všechny požadované hrany pro vrchol v_1 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é S transformovat na S', pak věta dokazuje, že původní soubor S není kreslitelný.

Odkazy

Reference

Související články

Erdős-Gallaiova věta

Kategorie:Grafové algoritmy