Algoritmo de Havel - Hakimi

El algoritmo Havel-Hakimi es un algoritmo recursivo para determinar si una lista dada de enteros aparece como una lista de todas las valencias de algún gráfico simple finito . Si la respuesta a esta pregunta es sí, la lista se llama gráfica .

El algoritmo fue propuesto por Václov Havel en 1955 y redescubierto por Luis Hakimi en 1962.

Algoritmo

El algoritmo se basa en el siguiente teorema.

Sea una lista finita de enteros no negativos en orden no creciente. Una lista es gráfica si, y solo si, la lista es gráfica. ${\displaystyle s,d_{1},\puntos,d_{s},t_{1},\puntos,t_{k))$ ${\displaystyle s,d_{1},\puntos,d_{s},t_{1},\puntos,t_{k))$ ${\displaystyle d_{1}-1,\puntos,d_{s}-1,t_{1},\puntos,t_{k))$

La operación descrita debe aplicarse alternativamente con el ordenamiento de la lista. Si en algún momento obtenemos una lista de ceros, entonces la lista original era gráfica. Si aparece un número negativo en la lista, entonces la lista original no era gráfica.

Ejemplos

Apliquemos el algoritmo a la lista . Alternativamente aplicamos el teorema y el ordenamiento. El hecho de que el resultado sea una lista de ceros significa que la lista es gráfica. ${\ estilo de visualización 4,4,3,3,2,2,1,1}$ ${\ estilo de visualización 4,4,3,3,2,2,1,1}$ ${\displaystyle {\begin{matriz}4&4&3&3&2&2&2&1&1\\3&2&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\\1&1&1&1&1&0\\0&1&1&0\\1&1&0}&0}trix$

Apliquemos el algoritmo a la lista . El hecho de que el resultado sea una lista de números negativos significa que la lista no es gráfica. ${\ estilo de visualización 7,6,3,3,2,2,1,1}$ ${\ estilo de visualización 7,6,3,3,2,2,1,1}$ ${\begin{matriz}7&6&3&3&2&2&1&1\\5&2&2&1&1&0&0\\1&1&0&0&-1&0\end{matriz))$

Véase también

Teorema de Erdős-Gallay

Notas

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), Sobre la realizabilidad de un conjunto de números enteros como grados de los vértices de un grafo lineal. I, Revista de la Sociedad de Matemáticas Industriales y Aplicadas , volumen 10: 496–506 .