Grafo etiquetado

En teoría de grafos, un grafo etiquetado es un grafo cuyos vértices tienen nombres o etiquetas.​ Estas etiquetas comúnmente son números enteros. En ocasiones, también se habla de grafo de aristas etiquetadas, de modo que son las aristas las que tienen etiquetas, y de este modo se distingue de un grafo de vértices etiquetados.​

El etiquetado de vértices o de aristas se define formalmente mediante una función desde el conjunto de vértices o aristas hacia un conjunto numérico o de etiquetas. Cuando las etiquetas de las aristas pertenecen a un conjunto ordenado (es decir, los números reales), ésta puede ser llamada como grafo ponderado.

Cuando es usado sin calificación, el término grafo etiquetado generalmente 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.​ Para muchas aplicaciones, a las aristas y los vértices le 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.​

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, es decir, un par de vértices puede ser conectado por varias aristas etiquetadas.​

Historia

La mayoría de los grafos etiquetados tienen sus orígenes en los etiquetados presentados por Alex Rosa en un artículo en 1967.​ Rosa identificó tres tipos de etiquetado, a los cuales llamó α-, β-, y ρ-etiquetado.​ 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

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

Un grafo armonioso es un grafo con k aristas que permiten una inyección de los vértices de G al grupo de enteros módulo 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

Una coloración por vértices para un grafo de Petersen, donde cada color representa una etiqueta.

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

Bibliografía

• Wasserman, Stanley; Faust, Katherine (2013) [1994]. Análisis de redes sociales: Métodos y aplicaciones. Madrid: Centro de Investigaciones Sociológicas. ISBN 978-84-7476-631-8. OCLC 871814053. 

• Datos: Q5597093