Havels algoritme - Hakimi

Havel-Hakimi- algoritmen er en rekursiv algoritme til at bestemme, om en given liste af heltal optræder som en liste over alle valenser af en endelig simpel graf . Hvis svaret på dette spørgsmål er ja, kaldes listen grafisk .

Algoritmen blev foreslået af Václov Havel i 1955 og genopdaget af Luis Hakimi i 1962.

Algoritme

Algoritmen er baseret på følgende teorem.

Lad der være en endelig liste over ikke-negative heltal i ikke-stigende rækkefølge. En liste er grafisk, hvis, og kun hvis, listen er grafisk. ${\displaystyle s,d_{1},\dots ,d_{s},t_{1},\dots ,t_{k))$ ${\displaystyle s,d_{1},\dots ,d_{s},t_{1},\dots ,t_{k))$ ${\displaystyle d_{1}-1,\dots ,d_{s}-1,t_{1},\dots ,t_{k))$

Den beskrevne handling skal anvendes skiftevis med rækkefølgen af listen. Hvis vi på et tidspunkt får en liste med nuller, så var den oprindelige liste en grafisk. Hvis der vises et negativt tal på listen, var den oprindelige liste ikke en grafisk.

Eksempler

Lad os anvende algoritmen på listen . Vi anvender skiftevis teoremet og rækkefølgen. At resultatet er en liste med nuller betyder, at listen er grafisk. $4,4,3,3,2,2,1,1$ $4,4,3,3,2,2,1,1$ ${\begin{matrix}4&4&3&3&2&2&1&1\\3&2&2&1&2&1&1\\3&2&2&2&2&1&1&1\\1&1&1&1&1&1\\1&1&1&1&1&1\\0&1&1&1&1&1\\}&0&1&1&1&1\\}&1&1&1\\\}&1&1&1\\$

Lad os anvende algoritmen på listen . At resultatet er en liste med negative tal betyder, at listen ikke er grafisk. $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))$

Se også

Erdős-Gallay-sætning

Noter

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), Om realiserbarheden af et sæt heltal som grader af hjørnerne af en lineær graf. I, Journal of the Society for Industrial and Applied Mathematics bind 10: 496–506 .