Secuencia de grados

En el campo matemático de la teoría de grafos, una secuencia de grados también llamada 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 del grafo.

Dos grafos no isomorfos pero con igual secuencia de grados (3,2,2,2,2,1,1,1).

La lista de grados es un invariante (topológico) de un grafo, aunque dos grafos con igual lista de grados no son necesariamente isomorfos.

Grafo G(V,A)	Conjuntos	Secuencia de grados
	V = { 1, 2, 3, 4, 5, 6 } A = { {1,1}, {1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6} }	(4,3,3,3,2,1)

Problema de la secuencia de enteros gráfica

Grafos simples

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] en 1960 resuelven el problema con su teorema de existencia:

Teorema de Erdős-Gallai

La secuencia de enteros $d_{i}\,$ con $i=1,...,n-1\,$ 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

$\sum _{i=1}^{k}d_{i}\leq k(k-1)+\sum _{i=k+1}^{n}\min(d_{i},k)$

Mientras que Havel[2] en 1955 y Hakimi[3] en 1962 nos entregan un teorema de construcción que justifica el Algoritmo de Havel-Hakimi para construir un grafo a partir de una secuencia de grados.

Teorema de Havel-Hakimi

Una secuencia de enteros $d_{1}\geq d_{2}\geq ...\geq d_{v}\geq 0$ es gráfica sí, y sólo sí también lo es la lista: $d_{2}-1,d_{3}-1,...,d_{d_{1}+1}-1,d_{d_{1}+2},...,d_{v}$ , que resulta de eliminar el primer elemento y restar una unidad a los siguientes $d_{1}$ valores de la lista.

Multigrafos

El problema de la secuencia de enteros gráfica para multigrafos o pseudografos es: dada una secuencia de enteros no negativos, determinar si es o no (multi)gráfica, es decir, es una secuencia de grados de un psedugrafo o multigrafo. Hakimi en 1962, nos entrega un resultado:

Teorema de Hakimi

Una secuencia de enteros $d_{1}\geq d_{2}\geq ...\geq d_{n}$ donde $n\geq 2$ es multigráfica (o pseudográfica) sí, y sólo sí la suma $\sum _{i=1}^{k}d_{i}$ es par y $d_{1}\leq d_{2}+...+d_{n}$ .

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..

Datos: Q6123324

Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.

[1] Erdős, P. ; Gallai, T. (1960). «Graphs with prescribed degree of vertices». Mat. Lapok 11. 264–274..

[2] Havel, V. (1955). «A remark on the existence of finite graphs.». Časopis Pest. Mat. 80. 477–480..

[3] 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..