Algoritmo de Havel-Hakimi

Algoritmo en teoría de grafos

El algoritmo Havel-Hakimi es un algoritmo de teoría de grafos que resuelve el problema de realización de grafos . Es decir, responde a la siguiente pregunta: Dada una lista finita de números enteros no negativos en orden no creciente, ¿existe una gráfica simple tal que su secuencia de grados sea exactamente esta lista? Un gráfico simple no contiene dobles aristas ni bucles . ^[1] La secuencia de grados es una lista de números en orden no creciente que indica el número de aristas incidentes en cada vértice del gráfico. ^[2] Si existe un gráfico simple exactamente para la secuencia de grados dada, la lista de números enteros se llama gráfico . El algoritmo Havel-Hakimi construye una solución especial si existe una gráfica simple para la secuencia de grados dada, o demuestra que no se puede encontrar una respuesta positiva. Esta construcción se basa en un algoritmo recursivo . El algoritmo fue publicado por Havel (1955) y posteriormente por Hakimi (1962).

el algoritmo

El algoritmo de Havel-Hakimi se basa en el siguiente teorema.

Sea una lista finita de números enteros no negativos que no sea creciente . Sea una segunda lista finita de números enteros no negativos que se reordena para que no sea creciente. La lista es gráfica si y sólo si la lista es gráfica. ${\displaystyle A=(s,t_{1},...,t_{s},d_{1},...,d_{n})}$ ${\displaystyle A'=(t_{1}-1,...,t_{s}-1,d_{1},...,d_{n})}$ ${\displaystyle A}$ ${\displaystyle A'}$

Si la lista dada es gráfica, entonces el teorema se aplicará la mayoría de las veces en cada paso posterior . Tenga en cuenta que puede ser necesario volver a ordenar esta lista. Este proceso finaliza cuando toda la lista consta de ceros. Sea un gráfico simple con la secuencia de grados : Sea el vértice tener grado ; que los vértices tengan grados respectivos ; Deje que los vértices tengan grados respectivos . En cada paso del algoritmo, se construyen las aristas de un gráfico con vértices ; es decir, si es posible reducir la lista a , entonces agregamos aristas . Cuando la lista no se puede reducir a una lista de números enteros no negativos en ningún paso de este enfoque, el teorema demuestra que la lista desde el principio no es gráfica. ${\displaystyle A}$ ${\displaystyle n-1}$ ${\displaystyle A:=A'}$ ${\displaystyle A'}$ ${\displaystyle G}$ ${\displaystyle A}$ ${\displaystyle S}$ ${\displaystyle s}$ ${\displaystyle T_{1},...,T_{s}}$ ${\displaystyle t_{1},...,t_{s}}$ ${\displaystyle D_{1},...,D_{n}}$ ${\displaystyle d_{1},...,d_{n}}$ ${\displaystyle T_{1},...,T_{s}}$ ${\displaystyle A}$ ${\displaystyle A'}$ ${\displaystyle \{S,T_{1}\},\{S,T_{2}\},\cdots ,\{S,T_{s}\}}$ ${\displaystyle A}$ ${\displaystyle A'}$ ${\displaystyle A}$

Prueba

El siguiente es un resumen basado en la prueba del algoritmo Havel-Hakimi en Invitation to Combinatorics (Shahriari 2022).

Para demostrar que el algoritmo Havel-Hakimi siempre funciona, supongamos que es gráfico y que existe un gráfico simple con la secuencia de grados . Luego agregamos un nuevo vértice adyacente a los vértices con grados para obtener la secuencia de grados . ${\displaystyle A'}$ ${\displaystyle G'}$ ${\displaystyle A'=(t_{1}-1,...,t_{s}-1,d_{1},...,d_{n})}$ ${\displaystyle v}$ ${\displaystyle s}$ ${\displaystyle t_{1}-1,...,t_{s}-1}$ ${\displaystyle A}$

Para probar la otra dirección, supongamos que es gráfica y que existe una gráfica simple con la secuencia de grados y los vértices . No sabemos a qué vértices son adyacentes , por lo que tenemos dos casos posibles. ${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle A=(s,t_{1},...,t_{s},d_{1},...,d_{n})}$ ${\displaystyle S,T_{1},...,T_{s},D_{1},...,D_{n}}$ ${\displaystyle s}$ ${\displaystyle S}$

En el primer caso, es adyacente a los vértices en . En este caso eliminamos con todas sus aristas incidentes para obtener la secuencia de grados . ${\displaystyle S}$ ${\displaystyle T_{1},...,T_{s}}$ ${\displaystyle G}$ ${\displaystyle S}$ ${\displaystyle A'}$

En el segundo caso, no es adyacente a algún vértice para algunos en . Luego podemos cambiar la gráfica para que sea adyacente manteniendo la misma secuencia de grados . Como tiene grado , el vértice debe ser adyacente a algún vértice en for : Sea el grado de . Lo sabemos , ya que la secuencia de grados está en orden no creciente. ${\displaystyle S}$ ${\displaystyle T_{i}}$ ${\displaystyle 1\leq i\leq s}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle S}$ ${\displaystyle T_{i}}$ ${\displaystyle A}$ ${\displaystyle S}$ ${\displaystyle s}$ ${\displaystyle S}$ ${\displaystyle D_{j}}$ ${\displaystyle G}$ ${\displaystyle 1\leq j\leq n}$ ${\displaystyle D_{j}}$ ${\displaystyle d_{j}}$ ${\displaystyle t_{i}\geq d_{j}}$ ${\displaystyle A}$

Dado que tenemos dos posibilidades: O o . Si , entonces al cambiar los lugares de los vértices y , podemos ajustar para que sea adyacente a en lugar de Si , entonces como es adyacente a más vértices que , dejemos que otro vértice sea adyacente y no . Luego podemos ajustar eliminando los bordes y y agregando los bordes y . Esta modificación conserva la secuencia de grados de , pero el vértice ahora es adyacente a en lugar de . De esta manera, cualquier vértice no conectado se puede ajustar en consecuencia para que sea adyacente mientras se mantiene la secuencia de grados original de . Por lo tanto, cualquier vértice no conectado se puede conectar usando el método anterior, y luego tenemos el primer caso una vez más, a través del cual podemos obtener la secuencia de grados . Por tanto, es gráfico si y sólo si también lo es. ${\displaystyle t_{i}\geq d_{j}}$ ${\displaystyle t_{i}=d_{j}}$ ${\displaystyle t_{i}>d_{j}}$ ${\displaystyle t_{i}=d_{j}}$ ${\displaystyle T_{i}}$ ${\displaystyle D_{j}}$ ${\displaystyle G}$ ${\displaystyle S}$ ${\displaystyle T_{i}}$ ${\displaystyle D_{j}.}$ ${\displaystyle t_{i}>d_{j}}$ ${\displaystyle T_{i}}$ ${\displaystyle D_{j}}$ ${\displaystyle W}$ ${\displaystyle T_{i}}$ ${\displaystyle D_{j}}$ ${\displaystyle G}$ ${\displaystyle \left\{S,D_{j}\right\}}$ ${\displaystyle \left\{T_{i},W\right\}}$ ${\displaystyle \left\{S,T_{i}\right\}}$ ${\displaystyle \left\{W,D_{j}\right\}}$ ${\displaystyle G}$ ${\displaystyle S}$ ${\displaystyle T_{i}}$ ${\displaystyle D_{j}}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle T_{i}}$ ${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle A'}$ ${\displaystyle A}$ ${\displaystyle A'}$

Ejemplos

Sea una secuencia de grados finitos y no creciente de números enteros no negativos. Para comprobar si esta secuencia de grados es gráfica, aplicamos el algoritmo de Havel-Hakimi: ${\displaystyle 6,3,3,3,3,2,2,2,2,1,1}$

Primero, eliminamos el vértice con el grado más alto, en este caso, y todos sus bordes incidentes para obtener (asumiendo que el vértice con el grado más alto es adyacente a los vértices con el siguiente grado más alto). Reorganizamos esta secuencia en orden no creciente para obtener . Repetimos el proceso, eliminando el vértice con el siguiente grado más alto para obtener y reorganizando para obtener . Continuamos con esta eliminación para obtener y luego . Esta secuencia es claramente gráfica, como es la gráfica simple de vértices aislados. ${\displaystyle 6}$ ${\displaystyle 2,2,2,2,1,1,2,2,1,1}$ ${\displaystyle 6}$ ${\displaystyle 2,2,2,2,2,2,1,1,1,1}$ ${\displaystyle 1,1,2,2,2,1,1,1,1}$ ${\displaystyle 2,2,2,1,1,1,1,1,1}$ ${\displaystyle 1,1,1,1,1,1,1,1}$ ${\displaystyle 0,0,0,0,0,0,0,0}$ ${\displaystyle 8}$

Para mostrar un ejemplo de una secuencia no gráfica, sea una secuencia de grados finitos y no creciente de números enteros no negativos. Aplicando el algoritmo, primero eliminamos el vértice de grado y todos sus bordes incidentes para obtener . Ya sabemos que esta secuencia de grados no es gráfica, ya que afirma tener vértices con un vértice no adyacente a ninguno de los otros vértices; por tanto, el grado máximo de los demás vértices es . Esto significa que dos de los vértices están conectados a todos los demás vértices con excepción del aislado, por lo que el grado mínimo de cada vértice debe ser ; sin embargo, la secuencia afirma tener un vértice con grado . Por tanto, la secuencia no es gráfica. ${\displaystyle 6,5,5,4,3,2,1}$ ${\displaystyle 6}$ ${\displaystyle 4,4,3,2,1,0}$ ${\displaystyle 6}$ ${\displaystyle 4}$ ${\displaystyle 2}$ ${\displaystyle 1}$

Por el bien del algoritmo, si tuviéramos que reiterar el proceso, obtendríamos que aún más claramente no es gráfico. Un vértice afirma tener un grado de y, sin embargo, sólo otros dos vértices tienen vecinos. Por tanto, la secuencia no puede ser gráfica. ${\displaystyle 3,2,1,0,0}$ ${\displaystyle 3}$

Ver también

• Teorema de Erdős-Gallai

Notas

1. De Shahriari (2022, p. 48): " Definición 2.17 (Gráficos y subgrafos). Una gráfica simple (o simplemente una gráfica ) G es un par de conjuntos ( V, E ) donde V es un conjunto no vacío llamado conjunto de vértices de G , y E es un conjunto (posiblemente vacío) de pares desordenados de elementos distintos de V. El conjunto E se llama conjunto de aristas de G. Si el número de vértices de G es finito, entonces G es un gráfico finito (o un gráfico simple finito )".
2. De Shahriari (2022, p. 355): " Definición 10.6 (La secuencia de grados de un gráfico; Secuencias gráficas). La secuencia de grados de un gráfico es la lista de los grados de sus vértices en orden no creciente. Un no- Una secuencia creciente de números enteros no negativos se llama gráfica si existe una gráfica simple cuya secuencia de grados es precisamente esa secuencia”.

Referencias

• Havel, Václav (1955), "Un comentario sobre la existencia de gráficos finitos", Časopis pro pěstování matematiky (en checo), 80 : 477–480
• Hakimi, SL (1962), "Sobre la realizabilidad de un conjunto de números enteros como grados de los vértices de un gráfico lineal. I", Revista de la Sociedad de Matemáticas Industriales y Aplicadas , 10 : 496–506, MR  0148049.
• Shahriari, Shahriar (2022), Invitación a la combinatoria, Cambridge U. Press.
• Oeste, Douglas B. (2001). Introducción a la teoría de grafos. Segunda edicion. Prentice Hall, 2001. 45-46.