Secuencia gráfica
Este algoritmo permite saber si un grafo se puede graficar. En primer lugar, hay que recordar que la existencia de un grafo depende de un teorema de existencia. Este teorema dice que para que un grafo exista, el número de vértices de grado impar tiene que ser par. Pero su existencia no garantiza sea graficable. Es por ello que se aplica el teorema de Havel Hakimi.
El algoritmo de Havel Hakimi se aplica sobre la secuencia gráfica. Una secuencia gráfica es el conjunto de grados de los vértices del grafo. Para aplicar el algoritmo hay que seguir los siguientes pasos:
Paso 1: se ordenan los valores en orden decreciente
Paso 2: se elimina el primer valor y se resta 1 a tantos valores como valor tenía el grado eliminado
Paso 3: se ordenan los valores de nuevo y se vuelve al paso 2
Una secuencia es graficable cuando después de aplicar el algoritmo tantas veces como sea posible, los valores restantes son 0. En caso de aparecer algún valor -1, el grafo no puede ser dibujado.
Veamos un ejemplo de aplicación de este algoritmo:
Supongamos la siguiente secuencia gráfica: 3, 2, 2, 3, 1, 1
Paso 1: 3, 3, 2, 2, 1, 1
Paso 2: 2, 1, 1, 1, 1
Paso 3: 0, 0, 1, 1
Paso 4: 1, 1, 0, 0
Paso 5: 0, 0, 0
Como la secuencia final está compuesta únicamente por 0, la secuencia es graficable y por tanto, el grafo, se puede dibujar.
Hasta aquí, la aplicación del algoritmo de Havel Hakimi. En la siguiente entrada trataremos los algoritmos BFS y DFS para explorar la conectividad de los grafos. Y como siempre os adjuntamos el enlace al donde explicamos este mismo post. Y como siempre podéis visitar nuestra web si necesitáis apoyo en alguna de vuestras asignaturas.