HAVEL-HAKIMI

es interesante saber cueando una lsita de enteros es o no grafica, o dicho en otras palabras es o no la lista de grados de un cierto grafo. Havel y Hakimi resolvieron esta cuestion a manera independiente en los años 1955 y 1962: una lista de enteros D1>=D2>=...>=Dv>=0 es grafica sii asimismo lo es la lista (presumiblemente no ordenada)

D2-1,D3-1....Dd1+1-1,Dd1+2,Dd1+3...,Dv

que se obtiene aleliminar D1 y restar una unidad a los D1 siguientes valores comprendidos entre D2 y Dd1+1.

en otras palabras si una lsita de enteros no negativosD1>=D2>=...>=Dv>=0 es grafica, siempre existe un grafo G(V,A) de vertices V={x1,...,xv} de manera que d(x1)=d1 y x1 es adyacente a los d1 vertices que le siguen. y reciprocamente, esta propiedad caracteriza completamente las listas que son grafixas.

asi pues, se puede diseñar un algoritmo sencillo , de complejidad lineal en el numero de vertices, que devuelve como salida si la lista de enteros es o no grafica: y que, en caso afirmativo, provee adicionalmente un metodo para construir un grafo cuya lista de grados coincide con la lista grafica de entrada.

ALGORITMO DE HAVEL-HAKIMI

ENTRADA:lista l=(d1,...,dn) con D1>=...>=Dv>=0.

P1   k=1

P2   mientras la lista k=(k1,..,kn) tengan entradas positivas hacer

P3   eliminar de k la primera entrada, k1

P4   restar una unidad a las primeras k1 entradas de la lita resultante

P5  k= reordenar la nueva lista asi obtenida en orden decreciente

P6  fin mientras

SALIDA: si la lista es nula entonces la lista inicial es grafica, en otro caso no lo es.

En verdad, los pasos P3 y P4 del algoritmo anterior consisten en pasar de la lista k=(K1,...,kn) a la lista   k(k2-1,...,kk1+1-1,k1+2,...,kn).

Caso de que el algoritmo devuelva una respuesta afirmativa, desandando el proceso que se ha descrito se puede construir sin dificultad un grafo cuya lista de grados es la lista inicial. Así, en este proceso de reconstruccion, cada entrada k1 suprimida en la lista se traduce en la aparicion de un nuevo vertice, adyacente a los k1 vertices cuyas valencias corresponden a las que han sido sustraidas tras la eliminacion de k1.

en conclusion, la lista de entrada es la grafica. para encontrar la realizacion de un grafo que tenga por lista de grados la lista de entrada andamos hacia atras el procediemiento seguido en el algoritmo. Como quiera que el proceso incluye reodernaciones de las valencias (y por tanto de los vertices).