Grafo etiquetado

Grafo etiquetado

En matemáticas, en la disciplina de teoría de grafos, un grafo etiquetado es la asignación de etiquetas, tradicionalmente representada mediante enteros, a las aristas or vértices, o ambos, de un grafo.[1]

Formalmente, dado un grafo G, un vértice etiquetado es una función que hace corresponde vértices de G a un conjunto de etiquetas. Un grafo con tal función definida es llamado grafo de vértices etiquetados. De la misma manera, una arista etiquetada es una función de asignación de aristas de G tal conjunto de «etiquetas». En este caso, G es llamado como grafo de aristas etiquetadas. Cuando las etiquetas de las aristas pertenecen a un conjunto ordenado (p.e., los números reales), ésta puede ser llamada como grafo ponderado.

Cuando es usado sin calificación, el término grafo etiquetado reneralmente se refiere a un grafo con vértices etiquetados con todas las etiquetas distintas. Tal grafo puede ser equivalentemente etiquetado mediante enteros consecutivos {1, ..., n}, donde n es el número de vértices en el grafo.[1] Para muchas aplicaciones, a las aristas y los vérticesle corresponde etiquetas que tienen un significado en el dominio asociado. Por ejemplo, las aristas pueden ser asignadas mediante pesos que representan el «coste» de atravesar entre los vértices implicados.[2]

En la definición de arriba se entiende como grafo un grafo simple indirecto finito. Sin embargo, la noción de etiquetado puede ser aplicada a todas las extensiones y generalizaciones de grafos. Por ejemplo, en teoría de autómatas y teoría de lenguaje formal es conveniente considerar multigrafos etiquetados, p.e., un par de vértices puede ser conectado por varias aristas etiquetadas.[3]

Contenido

Historia

La mayoría de los grafos etiquetados tienen sus origenesen los etiquetados presentados por Alex Rosa en un artículo en 1967.[4] Rosa identificó tres tipos de etiquetado, a los cuales llamó α-, β-, y ρ-etiquetado.[5] Los β-etiquetados fueron más tarde renombrados como elegantes por S.W. Golomb y el nombre se ha hecho popular desde entonces.

Casos especiales

Etiquetado elegante

Artículo principal: Etiquetado elegante
Un etiquetado elegante. Las etiquetas de los vértices están en negro, las etiquetas de las aristas en rojo.

Un grafo es denominado como elegante cuando sus vértices son etiquetados desde 0 a \|E\|, el tamaño del grafo, y este etiquetado induce un etiquetado de aristas desde 1 a \|E\|. Para cualquier arista e, los etiquetas de e son la diferencia positiva entre dos vértices incidentes con e. En otras palabras, si e es incidente con los vértices etiquetados k y j, e será etiquetado como \|k - j\|. Así pues, un grafo G: = (V,E) es elegante si y sólo si existe una inyección que induce una biyección de E a los enteros positivos hasta \|E\|.

En su trabajo original, Rosa demostró que todos los grafos eulerianos con órden equivalente a 1 o 2 (mod 4) no son elegantes. El si ciertas familias de grafos son elegantes o no es una área de la teoría de grafos que está bajo intenso estudio. Podría decirse que, la conjetura no demostrada más grande de etiquetado de grafos es la conjetura de Ringel-Kotzig, la cual conjetura que todos los árboles son elegantes. Ésto ha sido demostrado para todos los caminos, orugas, y muchas otras familias infinitas de los árboles. El mismo Kotzig ha llamado al esfuerzo de demostrar la conjetura una «enfermedad».

Etiquetado armonioso

Artículo principal: Etiquetado de aristas elegante

Un grafo armonioso es un grafo con k aristas que permiten una inyección de los vértices de G al grupo de enteros modulo k que induce una biyección entre las aristas de G y los enteros positivos hasta \|E\|. Para cualquier arista e, los etiquetados de e son la suma de las etiquetas de dos vértices incidentes con e (mod q).

Coloración de grafos

Artículo principal: Coloración de grafos

La coloración de grafos es un caso especial de grafos etiquetados, tales que los vértices adjacentes y las aristas coincidentes deben tener diferentes etiquetas.

Referencias

  1. a b Weisstein, Eric W. «Labeled graph» (en inglés). MathWorld. Wolfram Research.
  2. "Different Aspects of Coding Theory", by Robert Calderbank (1995) ISBN 0-8218-0379-4, p. 53"
  3. "Developments in Language Theory", Proc. 9th. Internat.Conf., 2005, ISBN 3-540-26546-5, p. 313
  4. Gallian, J.. A Dynamic Survey of Graph Labelings, 1996-2005. The Electronic Journal of Combinatorics. 
  5. Rosa, A.. On certain valuations of vertices in a graph. 
  • Rosa, A. "On certain valuations of the vertices of a graph." Theory of Graphs (Internat. Symposium, Rome, July 1966), Gordon and Breach, N. Y. and Dunod Paris. (1967) 349-355.
  • Gallian, Joseph A. "A Dynamic Survey of Graph Labeling." The Electronic Journal of Combinatorics (2005). 20 Dec. 2006 [1].

Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Grafo — Para otros usos de este término, véase Grafo (desambiguación). Para la teoría en torno a este objeto matemático, véase Teoría de grafos. Grafo etiquetado con 6 vértices y 7 aristas. En matemáticas y ciencias de la computación, un grafo (del …   Wikipedia Español

  • Grafo línea — En teoría de grafos, el grafo línea, de línea, lineal o representativo[1] L(G) de un grafo no dirigido G es un grafo que representa las adyacencias entre las aristas de G. Su nombre se debe a un artículo de Harary y Norman (1960), aunque… …   Wikipedia Español

  • Multigrafo — Un multigrafo con múltiples aristas (en rojo) y tres bucles (en azul). No todos los autores permiten multigrafos con bucles. Un multigrafo o pseudografo es un grafo que está facultado para tener aristas múltiples; es decir, aristas que relacionan …   Wikipedia Español

  • Teoría de Matrices — Saltar a navegación, búsqueda La teoría de matrices es un rama de las matemáticas que se centra en el estudio de matrices. Inicialmente una rama secundaria del álgebra lineal, ha venido cubriendo los temas relacionados con la teoría de grafos, el …   Wikipedia Español

  • Teoría de matrices — Se ha sugerido que este artículo o sección sea fusionado en matriz (matemática) (discusión). Una vez que hayas realizado la fusión de artículos, pide la fusión de historiales aquí. La teoría de matrices es un rama de las matemáticas que se centra …   Wikipedia Español

  • Clases de complejidad P y NP — Diagrama de clases de complejidad para el caso en que P ≠ NP. La existencia de problemas fuera tanto de P como de NP completos en este caso fue determinada por Ladner.[1] La relación entre las clases de complejidad P …   Wikipedia Español

  • 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

  • Árbol (teoría de grafos) — Para otros usos de este término, véase Árbol (desambiguación). Árbol Árbol etiquetado con 6 vértices y 5 aristas. El único camino simple que conecta los vértices 2 y 6 es 2 4 5 6 …   Wikipedia Español

  • NP (Complejidad computacional) — Saltar a navegación, búsqueda Los recursos comúnmente estudiados en complejidad computacional son: – El tiempo: mediante una aproximación al número de pasos de ejecución que un algoritmo emplea para resolver un problema. – El espacio: mediante… …   Wikipedia Español

  • NP (clase de complejidad) — En teoría de la complejidad computacional, NP es el acrónimo en inglés de nondeterministic polynomial time ( tiempo polinomial no determinista ). Es el conjunto de problemas que pueden ser resueltos en tiempo polinómico por una máquina de Turing… …   Wikipedia Español

Compartir el artículo y extractos

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