Algoritmo de Havel-Hakimi

El algoritmo de 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 enteros no negativos en orden no creciente, ¿existe un grafo simple tal que su secuencia de grados sea exactamente esta lista? Un grafo simple no contiene aristas dobles 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 a cada vértice del grafo. ^{[ 2 ]} Si existe un grafo simple para la secuencia de grados dada, la lista de enteros se llama gráfico . El algoritmo de Havel-Hakimi construye una solución especial si existe un grafo 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) .

Algoritmo

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

Teorema . ^{[ 3 ]} Sea $A=(s,t_{1},...,t_{s},d_{1},...,d_{n})$ Sea una lista finita de enteros no negativos que no es creciente . $A'=(t_{1}-1,...,t_{s}-1,d_{1},...,d_{n})$ Sea una segunda lista finita de enteros no negativos que se reordena para que no sea creciente. Lista $A$ es gráfico si y solo si lista $A'$ es gráfico.

Si la lista dada $A$ es gráfico, entonces el teorema se aplicará como máximo $n-1$ Los tiempos se establecen en cada paso siguiente. $A:=A'$ Tenga en cuenta que puede ser necesario ordenar esta lista nuevamente. Este proceso termina cuando toda la lista $A'$ consta de ceros. Sea $G$ Sea un grafo simple con la secuencia de grados $A$ : Sea el vértice $S$ tener título $s$ ; sean los vértices $T_{1},...,T_{s}$ poseen los títulos respectivos $t_{1},...,t_{s}$ ; sean los vértices $D_{1},...,D_{n}$ poseen los títulos respectivos $d_{1},...,d_{n}$ En cada paso del algoritmo, se construyen las aristas de un grafo con vértices. $T_{1},...,T_{s}$ —es decir, si es posible reducir la lista $A$ a $A'$ , luego agregamos bordes $\{S,T_{1}\},\{S,T_{2}\},\cdots ,\{S,T_{s}\}$ Cuando la lista $A$ no se puede reducir a una lista $A'$ de enteros no negativos en cualquier paso de este enfoque, el teorema demuestra que la lista $A$ Desde el principio no es gráfico.

Prueba

A continuación se presenta un resumen basado en la demostración del algoritmo de Havel-Hakimi en Invitation to Combinatorics (Shahriari 2022).

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

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

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

En el segundo caso, $S$ no es adyacente a algún vértice $T_{i}$ para algunos $1\leq i\leq s$ en $G$ Entonces podemos cambiar el gráfico. $G$ de modo que $S$ está adyacente a $T_{i}$ manteniendo la misma secuencia de grados $A$ . Desde $S$ tiene título $s$ , el vértice $S$ debe ser adyacente a algún vértice $D_{j}$ en $G$ para $1\leq j\leq n$ : Sea el grado de $D_{j}$ ser $d_{j}$ Lo sabemos. $t_{i}\geq d_{j}$ , como la secuencia de grados $A$ está en orden no creciente.

Desde $t_{i}\geq d_{j}$ Tenemos dos posibilidades: o $t_{i}=d_{j}$ , o $t_{i}>d_{j}$ . Si $t_{i}=d_{j}$ , luego intercambiando los lugares de los vértices $T_{i}$ y $D_{j}$ podemos ajustar $G$ de modo que $S$ está adyacente a $T_{i}$ en lugar de $D_{j}.$ Si $t_{i}>d_{j}$ , entonces desde $T_{i}$ es adyacente a más vértices que $D_{j}$ , dejemos otro vértice $W$ estar adyacente a $T_{i}$ y no $D_{j}$ Entonces podemos ajustar $G$ eliminando los bordes $\left\{S,D_{j}\right\}$ y $\left\{T_{i},W\right\}$ y añadiendo los bordes $\left\{S,T_{i}\right\}$ y $\left\{W,D_{j}\right\}$ Esta modificación conserva la secuencia de grados de $G$ , pero el vértice $S$ ahora está adyacente a $T_{i}$ en lugar de $D_{j}$ De esta manera, cualquier vértice no conectado a $S$ se puede ajustar en consecuencia para que $S$ está adyacente a $T_{i}$ manteniendo la secuencia de grados original $A$ de $G$ . Por lo tanto, cualquier vértice no conectado a $S$ puede conectarse a $S$ Utilizando el método anterior, volvemos a tener el primer caso, a través del cual podemos obtener la secuencia de grados. $A'$ . Por eso, $A$ es gráfico si y solo si $A'$ También es gráfico.

Ejemplos

Dejar $6,3,3,3,3,2,2,2,2,1,1$ Sea una secuencia de grados finita y no creciente de enteros no negativos. Para comprobar si esta secuencia de grados es gráfica, aplicamos el algoritmo de Havel-Hakimi:

Primero, eliminamos el vértice con el grado más alto; en este caso, $6$ — y todos sus bordes de incidentes para obtener $2,2,2,2,1,1,2,2,1,1$ (suponiendo que el vértice con el grado más alto es adyacente al $6$ vértices con el siguiente grado más alto). Reorganizamos esta secuencia en orden no creciente para obtener $2,2,2,2,2,2,1,1,1,1$ Repetimos el proceso, eliminando el vértice con el siguiente grado más alto para obtener $1,1,2,2,2,1,1,1,1$ y reorganizando para obtener $2,2,2,1,1,1,1,1,1$ . Continuamos con esta eliminación para obtener $1,1,1,1,1,1,1,1$ , y luego $0,0,0,0,0,0,0,0$ Esta secuencia es claramente gráfica, ya que es el gráfico simple de $8$ vértices aislados.

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

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

Véase también

Teorema de Erdős-Gallai

Notas

↑ De Shahriari (2022, p. 48): " Definición 2.17 (Grafos y subgrafos). Un grafo simple (o simplemente un grafo ) 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 no ordenados 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 grafo finito (o un grafo simple finito )."
↑ De Shahriari (2022, p. 355): « Definición 10.6 (La secuencia de grados de un grafo; secuencias gráficas). La secuencia de grados de un grafo es la lista de los grados de sus vértices en orden no creciente. Una secuencia no creciente de enteros no negativos se denomina gráfica si existe un grafo simple cuya secuencia de grados es precisamente esa secuencia.»
↑ West (2001), Teorema 1.3.31.

Referencias

Havel, Václav (1955), "Un comentario sobre la existencia de grafos finitos" , Časopis pro pěstování matematiky (en checo), 80 (4): 477– 480, doi : 10.21136/CPM.1955.108220
Hakimi, SL (1962), "Sobre la realizabilidad de un conjunto de enteros como grados de los vértices de un grafo lineal. I", Journal of the Society for Industrial and Applied Mathematics , 10 (3): 496–506 , doi : 10.1137/0110037 , MR 0148049 .
Shahriari, Shahriar (2022), Invitación a la combinatoria, Cambridge U. Press.
West, Douglas B. (2001). Introducción a la teoría de grafos. Segunda edición. Prentice Hall, 2001. 45–46.

[1] De Shahriari (2022, p. 48): " Definición 2.17 (Grafos y subgrafos). Un grafo simple (o simplemente un grafo ) 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 no ordenados 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 grafo finito (o un grafo simple finito )."

[2] De Shahriari (2022, p. 355): « Definición 10.6 (La secuencia de grados de un grafo; secuencias gráficas). La secuencia de grados de un grafo es la lista de los grados de sus vértices en orden no creciente. Una secuencia no creciente de enteros no negativos se denomina gráfica si existe un grafo simple cuya secuencia de grados es precisamente esa secuencia.»

[3] West (2001), Teorema 1.3.31.

[ 1 ]

[ 2 ]

[ 3 ]