El algoritmo de Havel-Hakimi es un algoritmo en 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 una gráfica simple tal que su secuencia de grados sea exactamente esta lista? Un gráfico simple no contiene aristas ni bucles dobles. [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 para exactamente la secuencia de grados dada, la lista de números enteros se llamagráfico . El algoritmo de Havel-Hakimi construye una solución especial si existe un gráfico 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 más tarde por Hakimi (1962) .
El algoritmo
El algoritmo de Havel-Hakimi se basa en el siguiente teorema.
Dejar ser una lista finita de enteros no negativos que no aumenta . Dejarser una segunda lista finita de enteros no negativos que se reordena para no aumentar. Lista es gráfico si y solo si lista es gráfico.
Si la lista dada es gráfico, entonces el teorema se aplicará como máximo tiempos ajustados en cada paso adicional . Tenga en cuenta que puede ser necesario volver a ordenar esta lista. Este proceso termina cuando toda la listaconsta de ceros. Dejar ser un gráfico simple con la secuencia de grados : Deja el vértice tener grado ; deja los vértices tener títulos respectivos ; deja los vértices tener títulos respectivos . En cada paso del algoritmo, se construyen los bordes de un gráfico con vértices—Es decir, si es posible reducir la lista a , luego agregamos bordes . Cuando la lista no se puede reducir a una lista de enteros no negativos en cualquier paso de este enfoque, el teorema demuestra que la lista desde el principio no es gráfico.
Prueba
El siguiente es un resumen basado en la prueba del algoritmo de Havel-Hakimi en Invitación a la combinatoria (Shahriari 2022).
Para demostrar que el algoritmo de Havel-Hakimi siempre funciona, suponga que es gráfico, y existe un gráfico simple con la secuencia de grados . Luego agregamos un nuevo vértice adyacente a la vértices con grados para obtener la secuencia de grados .
Para probar la otra dirección, suponga que es gráfico, y existe un gráfico simple con la secuencia de grados y vértices . No sabemos cual los vértices son adyacentes a , por lo que tenemos dos casos posibles.
En el primer caso, es adyacente a los vértices en . En este caso, eliminamos con todos sus bordes incidentes para obtener la secuencia de grados .
En el segundo caso, no es adyacente a algún vértice para algunos en . Entonces podemos cambiar el gráfico así que eso es adyacente a manteniendo la misma secuencia de grados . Desde tiene grado , el vértice debe ser adyacente a algún vértice en por : Sea el grado de ser . Sabemos, como la secuencia de grados está en orden no creciente.
Desde , tenemos dos posibilidades: O , o . Si, luego cambiando los lugares de los vértices y , podemos ajustar así que eso es adyacente a en vez de Si , entonces desde es adyacente a más vértices que , deja otro vértice ser adyacente a y no . Entonces podemos ajustar quitando 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 vez de . De esta forma, cualquier vértice no conectado a se puede ajustar en consecuencia para que es adyacente a manteniendo la secuencia de grados original de . Por lo tanto, cualquier vértice no conectado a se puede conectar a 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 eso, es gráfico si y solo si también es gráfico.
La complejidad temporal del algoritmo es.
Ejemplos de
Dejar ser una secuencia de grados finitos no creciente de números enteros no negativos. Para probar 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, - y todos sus bordes incidentes para obtener (asumiendo que el vértice de mayor grado es adyacente al 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 conseguir . Continuamos esta eliminación para obtener, y entonces . Esta secuencia es claramente gráfica, ya que es la gráfica simple de vértices aislados.
Para mostrar un ejemplo de una secuencia no gráfica, dejemos ser una secuencia de grados finitos no creciente de números enteros no negativos. Aplicando el algoritmo, primero eliminamos el grado vértice y todos sus bordes incidentes para obtener . Ya sabemos que esta secuencia de grados no es gráfica, ya que afirma tenervértices con un vértice no adyacente a ninguno de los otros vértices; así, el grado máximo de los otros vértices es. 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; sin embargo, la secuencia afirma tener un vértice con grado. Por tanto, la secuencia no es gráfica.
Por el bien del algoritmo, si tuviéramos que reiterar el proceso, obtendríamos que es aún más claramente no gráfico. Un vértice afirma tener un grado dey, sin embargo, solo otros dos vértices tienen vecinos. Por tanto, la secuencia no puede ser gráfica.
Ver también
Notas
- ^ De Shahriari (2022, p. 48): " Definición 2.17 (Gráficos y subgráficos). Un gráfico simple (o simplemente un gráfico ) 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 grafo finito (o un gráfico simple finito ) ".
- ^ De Shahriari (2022, p. 355): " Definición 10.6 (La secuencia de grados de una gráfica; Secuencias gráficas). La secuencia de grados de una gráfica es la lista de los grados de sus vértices en orden no creciente. La secuencia creciente de números enteros no negativos se llama gráfico , si existe un gráfico simple cuya secuencia de grados es precisamente esa secuencia ".
Referencias
- Havel, Václav (1955), "Una observación 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 grafo 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.
- West, Douglas B. (2001). Introducción a la teoría de grafos. Segunda edicion. Prentice Hall, 2001. 45-46.