Havlův algoritmus - Hakimi

Havel-Hakimiho algoritmus je rekurzivní algoritmus pro určení, zda daný seznam celých čísel vypadá jako seznam všech valenčních hodnot nějakého konečného jednoduchého grafu . Pokud je odpověď na tuto otázku ano, seznam se nazývá grafický .

Algoritmus navrhl Václov Havel v roce 1955 a znovu objevil Luis Hakimi v roce 1962.

Algoritmus

Algoritmus je založen na následující větě.

Nechť existuje konečný seznam nezáporných celých čísel v nerostoucím pořadí. Seznam je grafický tehdy a pouze tehdy, když je seznam grafický. ${\displaystyle s,d_{1},\tečky ,d_{s},t_{1},\tečky ,t_{k))$ ${\displaystyle s,d_{1},\tečky ,d_{s},t_{1},\tečky ,t_{k))$ ${\displaystyle d_{1}-1,\dots ,d_{s}-1,t_{1},\tečky ,t_{k))$

Popsaná operace by měla být aplikována střídavě s uspořádáním seznamu. Pokud v určitém okamžiku dostaneme seznam nul, pak původní seznam byl grafický. Pokud se v seznamu objeví záporné číslo, pak původní seznam nebyl grafický.

Příklady

Aplikujme algoritmus na seznam . Střídavě aplikujeme větu a uspořádání. Skutečnost, že výsledkem je seznam nul, znamená, že seznam je grafický. $4,4,3,3,2,2,1,1$ $4,4,3,3,2,2,1,1$ ${\displaystyle {\begin{matrix}4&4&3&3&2&2&1&1\\3&2&2&1&2&1&1\\3&2&2&2&1&1&1\\1&1&1&1&1&1\\1&1&1&1&1&1\\0&1&1&1&1\0&0\0\0\0&1&1&1\0$

Aplikujme algoritmus na seznam . Skutečnost, že výsledkem je seznam záporných čísel, znamená, že seznam není grafický. $7,6,3,3,2,2,1,1$ $7,6,3,3,2,2,1,1$ ${\begin{matrix}7&6&3&3&2&2&1&1\\5&2&2&1&1&0&0\\1&1&0&0&-1&0\end{matrix))$

Viz také

Erdősova-Gallayova věta

Poznámky

Havel, Václav (1955), POZNÁMKA O EXISTENCI KONEČNÝCH GRAFŮ , Časopis pro pěstování matematiky T. 80: 477–480 , < http://eudml.org/doc/19050 >
Hakimi, S. L. (1962), O realizovatelnosti množiny celých čísel jako stupňů vrcholů lineárního grafu. I, Journal of the Society for Industrial and Applied Mathematics , svazek 10: 496–506 .