Sucesiones

Sucesiones gráficas (Havel & Hakimi)
 
Este método desarrollado por Havel y Hakimi será el que implementemos en el proyecto. Es gráfico y está basado en la reconstrucción del grafo, el cualobtenemos tras ir insertando vértices y aristas en sucesivas iteraciones.
Condiciones
Las condiciones para que una sucesión de grados de un grafo sea gráfica son:
·        La suma debe ser par·        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).
·        Si la sucesiónt1-1, t2-1, t3-1,....., ts-1, d1, d2,......, dk es gráfica entonces también lo es la sucesión s, t1, t2, t3,....., ts, d1, d2,......, dk.

 
Si dos grafos son isomorfos entonces tienen la mismasucesió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 isomorfosporque 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.

Caracterización
La sucesión s, t1, t2, t3,....., ts,d1, d2,......, dk es gráfica Û lo es la sucesión t1-1, t2-1, t3-1,....., ts-1, d1, d2,......, dk
Demostración
 Sea G el grafo cuya sucesión es s, t1, t2, … , ts, d1, … ,dk y sean S, T1, T2, …Ts , D1, … ,Dklos vértices correspondientes
·        Si S es adyacente a T1, T2, …Ts, borramos S y el grafo H=G-{S} es el grafo buscado.

·        Si no es así, S no es adyacente a un Ti pero SÍ es adyacente a unvértice Dj con  ti ≥ dj

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 deDj. Eliminamos las aristas dibujadas con líneas continuas ( SDj, ZTi ) y creamos las discontinuas ( STi, ZDj ). Este grafo G1 tiene la misma sucesión grados en el vértice S pero tiene un vecino...