Secuencia de grados

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

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 d1 valores de la lista.

Referencias

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

Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Secuencia de Prüfer — En matemática combinatoria, la secuencia de Prüfer (o código de Prüfer) de un árbol etiquetado es una secuencia única asociada al árbol. La secuencia de un árbol con n vértices tiene longitud n − 2, y puede ser generada por un algoritmo iterativo …   Wikipedia Español

  • Secuencia principal — Diagrama Hertzsprung Russell. Se denomina secuencia principal a la región del diagrama de Hertzsprung Russell en la que se encuentran la mayor parte de las estrellas. Por esta razón, estas estrellas son llamadas de secuencia principal. Las… …   Wikipedia Español

  • Secuencia de Murphy — Se conoce con el nombre de Secuencia de Murphy a la presencia de: Dolor: que aparece en epigastrio o región periumbilical, que luego se traslada a fosa ilíaca derecha (FID). Vómito, náusea o anorexia. Fiebre o febrícola: que no excede los 38… …   Wikipedia Español

  • Grado (teoría de grafos) — Para otros usos de este término, véase Grado. Un grafo con vértices etiquetados según su grado. El vértice aislado se etiqueta con 0, pues su grado es igual a cero. En Teoría de grafos, el grado o valencia de un vértice es el número de aristas… …   Wikipedia Español

  • Planeta extrasolar — Saltar a navegación, búsqueda Cantidad de exoplanetas descubiertos hasta la fecha: 405.[1] Se denomina planeta extrasolar o exoplaneta a un …   Wikipedia Español

  • Teselación de Penrose — Una teselación de Penrose Una Teselación de Penrose o suelo de baldosas de Penrose es una teselación no periódica generada por un conjunto aperiódico de baldosas prototipo nombradas en honor a Roger Penrose, quien investigó esos conjuntos en la… …   Wikipedia Español

  • Teorema de Fortescue — El teorema de Fortescue o teorema de las componentes simétricas es uno de los teoremas más importantes en la ingeniería eléctrica. Se utiliza para simplificar el análisis de los sistemas de energía trifásicos desequilibrados, pues permite… …   Wikipedia Español

  • Sake — Barriles de sake en el Templo Itsukushima. El sake (酒, sake …   Wikipedia Español

  • Karate — Do 空手道 Gichin Funakoshi, considerado el padre del karate Do moderno, practicando con un poste para golpeo o makiwara …   Wikipedia Español

  • Escala musical — En un sentido general, se llama escala musical a la sucesión ordenada consecutivamente de todas las notas de un entorno sonoro particular (sea tonal o no); de manera simple y esquemática según la notación musical convencional pentagramada , estos …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”