Tarea 1: Algoritmo de Havel-Hakimi

Este método es gráfico y esta basado en la reconstrucción del grafo, el cual se obtiene al estar insertando vértices y aristas.

Las condiciones para llevar a cabo dicho algoritmo son los siguientes:

1.- La suma debe ser par.

2.- El valor máximo debe ser menor que la longitud. Por ejemplo la sucesión 6, 4, 4, 2, 1, 1 no es gráfica pues el valor mayor de la sucesión (6) es igual que la longitud de esta (6).

3.- Si la sucesión t₁-1, t₂-1, t₃-1,....., ts-1, d_1, d_2,......, d_k es gráfica entonces también lo es la sucesión s, t₁, t₂, t₃,....., ts, d_1, d_2,......, d_k.

Si dos grafos son isomorfos entonces tienen la misma sucesión de grados, pero que dos grafos tengan la misma sucesión de grados no quiere decir que sean isomorfos. Por ejemplo los dos siguiente grafos tienen la misma sucesión 4,4,3,2,2,2,1. Pero no son isomorfos porque por ejemplo en el grafo G los nodos de grado 4 no están unidos, mientras que en el grafo G' los nodos de grado 4 si lo están.

                                                        G                                   G´

     Caracterización:

Recordando una de las condiciones era que la sucesión s, t₁, t₂, t₃,....., ts, d_1, d_2,......, d_k es gráfica entonces tambien lo es la sucesión t₁-1, t₂-1, t₃-1,....., ts-1, d_1, d_2,......, d_k.  

     Demostracion:

Sea G el grafo cuya sucesión es s, t1, t2, … , ts, d1, … ,dk y sean S, T1, T2, …Ts , D1, … , Dk los vértices correspondientes entonces:

1.- Si S es adyacente a T1, T2, …Ts, borramos S y el grafo H=G-{S} es el grafo buscado.

2.-   Si no es así, S no es adyacente a un Ti pero SÍ es adyacente a un vértice Dj con  ti >/dsdsd dj

3.- Si ti= dj , basta intercambiar los papeles de Ti y de Dj. Si ti >dj,

Ti tiene más vecinos que Dj. Sea Z vecino de Ti pero no vecino de Dj. Eliminamos las aristas dibujadas con líneas continuas ( SD_j, ZT_i ) y creamos las discontinuas ( ST_i, ZD_j). Este grafo G1 tiene la misma sucesión grados en el vértice S pero tiene un vecino entre los Ti más que en el grafo G. 

Si en G' ya es S adyacente a T1, T2,…Ts, se procede como antes. Y si no lo es se repite el cambio discontinuas-continuas. Como s es finito se alcanza en algún momento un grafo Gm cuya sucesión es la dada.

Algoritmo:

Partiendo de una sucesión no creciente de enteros positivos o nulos para decidir si ésta es gráfica o no, lo que hay que hacer es aplicar la caracterización vista en el apartado anterior 2.2.2.2 hasta que suceda alguna de las dos situaciones siguientes:

·        Se alcanza una sucesión de 0's Þ la sucesión si es gráfica.

Se obtiene un número negativo Þ la sucesión no es gráfica.

Cita: Peñalver, Gregorio H. "Matematicas." Http://www.dma.fi.upm.es/gregorio/. Http://www.dma.fi.upm.es/gregorio/grafos/SucGrafCertifArboles/html/Sucesiones%20graficas.htm, 2 June 2004. Web. 13 Feb. 2015.