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.
La lista de grados es un invariante (topológico) de un grafo, aunque dos grafos con igual lista de grados no son necesariamente isomorfos.
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:
|
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.
|
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:
|
Referencias
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.