Algoritmus Havel – Hakimi - Havel–Hakimi algorithm
Tento článek obsahuje a seznam doporučení, související čtení nebo externí odkazy, ale jeho zdroje zůstávají nejasné, protože mu chybí vložené citace.Červen 2020) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
The Algoritmus Havel – Hakimi je algoritmus v teorie grafů řešení problém realizace grafu. To znamená, že odpovídá na následující otázku: Vzhledem k konečnému seznam nezáporné celá čísla, je tam a jednoduchý graf takový, že jeho sekvence stupňů je přesně tento seznam? Sekvence stupňů je seznam čísel, která pro každý vrchol grafu uvádějí, kolik sousedů má. Pro kladnou odpověď se volá seznam celých čísel grafický. Algoritmus vytvoří speciální řešení, pokud existuje, nebo prokáže, že nelze najít kladnou odpověď. Tato konstrukce je založena na a rekurzivní algoritmus. Algoritmus publikoval Havel (1955) a později Hakimi (1962).
Algoritmus
Algoritmus je založen na následující větě.
Nechat být konečný seznam nezáporných celých čísel nezvyšující se. Seznam je grafický právě tehdy, pokud jde o konečný seznam má nezáporná celá čísla a je grafický.
Pokud daný seznam je grafický, pak bude věta použita maximálně nastavení času v každém dalším kroku . Může být nutné tento seznam znovu seřadit. Tento proces končí, když celý seznam sestává z nul. V každém kroku algoritmu se vytvoří hrany grafu s vrcholy , tj. pokud je možné seznam zmenšit na , pak přidáme hrany . Když seznam nelze redukovat na seznam nezáporných celých čísel v každém kroku tohoto přístupu, věta dokazuje, že seznam od začátku není grafický.
The časová složitost algoritmu je .
Viz také
Reference
- Havel, Václav (1955), „Poznámka o existenci konečných grafů“, Časopis pro pěstování matematiky (v češtině), 80: 477–480
- Hakimi, S.L. (1962), "O realizovatelnosti množiny celých čísel jako stupňů vrcholů lineárního grafu. I", Deník Společnost pro průmyslovou a aplikovanou matematiku, 10: 496–506, PAN 0148049.
- West, Douglas B. (2001). Úvod do teorie grafů. Druhé vydání. Prentice Hall, 2001. 45-46.