- Secuencia de grados
-
En teoría de grafos, una secuencia de grados, sucesión gráfica o lista de grados de un grafo no-dirigido es una secuencia de números, los cuales son grados de los vértices de algún grafo.
La lista de grados es un invariante (topológica) de un grafo, aunque dos grafos con igual lista de grados no son necesariamente isomorfos.
Secuencia de enteros gráfica
Un problema interesante es determinar si una secuencia de enteros no-negativos cualquiera es o no gráfica, es decir, es una secuencia de grados de un grafo (simple). Erdős y Gallai[1] (1960) resuelven el problema con su teorema de existencia, mientras que Havel[2] (1955) y Hakimi[3] (1962) nos entregan un teorema de construcción que justifica el Algoritmo Havel-Hakimi para construir un grafo a partir de una secuencia de grados.
Teorema de Erdős-Callai. La secuencia de enteros
con 
es una secuencia de grados de un grafo simple, si y sólo si:- La suma de los enteros de la secuencia es par, y
Teorema de Havel-Hakimi. Una secuencia de enteros
es gráfica sí, y sólo sí también lo es la lista: 
, que resulta de eliminar el primer elemento y restar una unidad a los siguientes d1 valores de la lista.Referencias
- ↑ Erdős, P. ; Gallai, T. (1960). «Graphs with prescribed degree of vertices». Mat. Lapok 11. 264–274..
- ↑ Havel, V. (1955). «A remark on the existence of finite graphs.». Časopis Pest. Mat. 80. 477–480..
- ↑ Hakimi, S.L. (1962). «On the realizability of a set of integers as degrees of the vertices of a simple graph». J. SIAM Appl. Math 10. 496–506..
Wikimedia foundation. 2010.
