domingo, 8 de febrero de 2015

Algoritmo de  Havel-Hakimi

*Pasos del Algoritmo de  Havel-Hakimi:

-Sucesión decreciente de enteros no negativos.
-Se elimina el primer numero de la lista,es decir s.

-Se resta una unidad a los siguientes valores comprendidos entre t1 y df.

-Si alguno de los valores resulta negativo entonces quiere decir que el grafo no existe por lo tanto la sucesión no es gráfica.

-Se conecta en el grafo el vértice asociado a s con los vértices asociados a t1,t2,...,ts por medio de aristas.
En caso de que la lista no sea decreciente,se re ordenara sin confundir los nombres de los vértices.

-Se repite el paso 2 hasta que no queden números en la lista.

*Resuelve si la siguiente es una sucesión gráfica(5,5,4,4,3,2,1,1).

Esta sucesión no es gráfica puesto que es impar tomando en cuenta que el Lema del apretón de manos nos dice que "El numero de grados en una gráfica sin bucles debe ser par".