PASOS DEL ALGORITMO HAVEL-HAKIMI

PASOS DEL ALGORITMO HAVEL-HAKIMI

             1.      Primero comenzar con una sucesión decreciente de enteros no negativos

              y con un grafo vacío en el cual el número de vértices es igual a la cantidad de números en esa sucesión

             2.      Se elimina el número mayor de la lista “d1” y se resta una unidad a los siguientes  vértices de la lista 

           . Si alguno de los números e negativo significa que el grafo buscado no existe y la sucesión no es gráfica.

              3.      Conectamos en el grafo el vértice asociado a “d1” con los vértices asociados asocias a “t1, t2,… t” mediante aristas.

              4.      Si la lista no es decreciente la reordenamos pero se tiene que evitar confundir los nombres de los vértices.

              5.      Se regresa al paso 2 hasta que no haya números en la lista

En el ejemplo del video nos dan 7 números, 4 de estos son impares, es lo que nos dices el lema del apretón de manos, y el número mayor (5) es menor a la cantidad de números que hay (7). Se elimina el primero y se resta 1 a los demás y se conecta al primer vértice con los que correspondan. Después volvemos a eliminar el primero y le restamos uno a los demás, también se conecta a el segundo vértice con los correspondientes. Posteriormente ordenamos los vértices nulos y volvemos a eliminar el primer y unir a este con los vértices correspondientes. Por ultimo nos quedaron dos vértices, entonces al primero se le une con el ultimo y así es como se finaliza.