En la disciplina matemática de la teoría de grafos , el etiquetado de un gráfico es la asignación de etiquetas, tradicionalmente representadas por números enteros , a aristas y/o vértices de un gráfico . [1]
Formalmente, dado un gráfico G = ( V , E ) , el etiquetado de un vértice es una función de V para un conjunto de etiquetas; un gráfico con dicha función definida se llama gráfico etiquetado con vértices . Asimismo, un etiquetado de borde es una función de E para un conjunto de etiquetas. En este caso, el gráfico se llama gráfico de bordes etiquetados .
Cuando las etiquetas de los bordes son miembros de un conjunto ordenado (por ejemplo, los números reales ), se le puede llamar gráfico ponderado .
Cuando se usa sin calificación, el término gráfico etiquetado generalmente se refiere a un gráfico etiquetado con vértices con todas las etiquetas distintas. Un gráfico de este tipo puede etiquetarse de manera equivalente mediante números enteros consecutivos { 1,…, | V | } , donde | V | es el número de vértices del gráfico. [1] Para muchas aplicaciones, los bordes o vértices reciben etiquetas que son significativas en el dominio asociado. Por ejemplo, a los bordes se les pueden asignar pesos que representen el "coste" de atravesar entre los vértices incidentes. [2]
En la definición anterior, se entiende por gráfico un gráfico simple finito no dirigido. Sin embargo, la noción de etiquetado puede aplicarse a todas las extensiones y generalizaciones de gráficos. Por ejemplo, en teoría de autómatas y teoría del lenguaje formal es conveniente considerar multigrafos etiquetados , es decir, un par de vértices pueden estar conectados por varias aristas etiquetadas. [3]
La mayoría de los etiquetados de gráficos tienen su origen en los etiquetados presentados por Alexander Rosa en su artículo de 1967. [4] Rosa identificó tres tipos de etiquetado, a los que llamó etiquetados α , β y ρ . [5] Más tarde, Solomon Golomb cambió el nombre de las etiquetas β a "elegantes" , y el nombre ha sido popular desde entonces.
Un gráfico se conoce como elegante si sus vértices están etiquetados de 0 a | mi | , el tamaño del gráfico y si este etiquetado de vértices induce un etiquetado de bordes de 1 a | mi | . Para cualquier arista e , la etiqueta de e es la diferencia positiva entre las etiquetas de los dos vértices incidentes con e . En otras palabras, si e incide con los vértices etiquetados i y j , entonces e se etiquetará | yo - j | . Por tanto, una gráfica G = ( V , E ) es elegante si y sólo si existe una inyección de V a {0, ..., | E |} que induce una biyección de E a {1, ..., | mi |} .
En su artículo original, Rosa demostró que todos los gráficos eulerianos con tamaño equivalente a 1 o 2 ( mod 4 ) no son elegantes. Si ciertas familias de grafos son elegantes o no es un área de la teoría de grafos que se está estudiando extensamente. Podría decirse que la conjetura no probada más grande en el etiquetado de gráficos es la conjetura de Ringel-Kotzig, que plantea la hipótesis de que todos los árboles son elegantes. Esto ha sido probado para todos los caminos , orugas y muchas otras infinitas familias de árboles. El propio Anton Kotzig ha calificado el esfuerzo por demostrar la conjetura como una "enfermedad". [6]
Un etiquetado elegante de bordes en un gráfico simple sin bucles o múltiples bordes en p vértices y q bordes es un etiquetado de los bordes mediante enteros distintos en {1,…, q } tal que el etiquetado en los vértices inducido al etiquetar un vértice con la suma de las aristas incidentes tomadas módulo p asigna todos los valores de 0 a p − 1 a los vértices. Se dice que un gráfico G tiene "bordes elegantes" si admite un etiquetado con bordes elegantes.
Los etiquetados con bordes elegantes fueron introducidos por primera vez por Sheng-Ping Lo en 1985. [7]
Una condición necesaria para que un gráfico tenga bordes elegantes es la "condición de Lo":
Un "etiquetado armonioso" en un gráfico G es una inyección desde los vértices de G al grupo de números enteros módulo k , donde k es el número de aristas de G , que induce una biyección entre las aristas de G y los números módulo k por tomando la etiqueta de arista de una arista ( x , y ) como la suma de las etiquetas de los dos vértices x , y (mod k ) . Un "gráfico armonioso" es aquel que tiene un etiquetado armonioso. Los ciclos impares son armoniosos, al igual que los gráficos de Petersen . Se conjetura que todos los árboles son armoniosos si se permite la reutilización de una etiqueta de vértice. [8] El gráfico del libro de siete páginas K 1,7 × K 2 proporciona un ejemplo de un gráfico que no es armonioso. [9]
La coloración de gráficos es una subclase de etiquetado de gráficos. Los colores de vértices asignan diferentes etiquetas a los vértices adyacentes, mientras que los colores de bordes asignan diferentes etiquetas a los bordes adyacentes. [10]
Un etiquetado afortunado de un gráfico G es una asignación de números enteros positivos a los vértices de G de modo que si S ( v ) denota la suma de las etiquetas de los vecinos de v , entonces S es una coloración de vértices de G . El "número de la suerte" de G es el menor k tal que G tiene un etiquetado de la suerte con los números enteros {1,…, k }. [11]
