Etiquetado de gráficos
En la disciplina matemática de la teoría de grafos , un etiquetado de grafos es la asignación de etiquetas, tradicionalmente representadas por números enteros , a los bordes y / o vértices de un grafo . [1]
Formalmente, dado un gráfico , el etiquetado de un vértice es una función de un conjunto de etiquetas; un gráfico con una función de este tipo definida se denomina gráfico etiquetado con vértice . Asimismo, un etiquetado de borde es una función de un conjunto de etiquetas. En este caso, el gráfico se denomina gráfico de borde etiquetado .
Cuando las etiquetas de los bordes son miembros de un conjunto ordenado (por ejemplo, los números reales ), se le puede llamar un 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értice con todas las etiquetas distintas. Dicho gráfico puede ser etiquetado de manera equivalente por los números enteros consecutivos , donde es el número de vértices en el 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 "costo" de atravesar los vértices incidentes. [2]
En la definición anterior, se entiende que un gráfico es un gráfico simple finito no dirigido. Sin embargo, la noción de etiquetado se puede aplicar a todas las extensiones y generalizaciones de gráficos. Por ejemplo, en la teoría de autómatas y en la teoría del lenguaje formal , es conveniente considerar multigrafos etiquetados , es decir, un par de vértices puede estar conectado por varios bordes etiquetados. [3]
Historia
La mayoría de las etiquetas de gráficos tienen su origen en las etiquetas presentadas por Alexander Rosa en su artículo de 1967. [4] Rosa identificó tres tipos de etiquetas, a las que llamó etiquetas α , β y ρ . [5] Las etiquetas β fueron posteriormente renombradas como "agraciadas" por Solomon Golomb , y el nombre ha sido popular desde entonces.
Casos especiales
Etiquetado elegante
Un gráfico se conoce como elegante cuando sus vértices están etiquetados de 0 a | E |, el tamaño del gráfico, y este etiquetado induce un etiquetado de borde de 1 a | E |. Para cualquier arista e , la etiqueta de e es la diferencia positiva entre los dos vértices incidentes con e . En otras palabras, si e incide en los vértices etiquetados i y j , e se etiquetará | i - j |. Por lo tanto, un gráfico G = ( V , E ) es elegante si y solo si existe una inyección que induce una biyección de Ea los enteros positivos hasta | E |.
En su artículo original, Rosa demostró que todas las gráficas eulerianas con un tamaño equivalente a 1 o 2 ( mod 4) no son elegantes. Si ciertas familias de gráficos son elegantes o no, es un área de la teoría de grafos que se está estudiando extensamente. Podría decirse que la mayor conjetura no probada 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 familias infinitas de árboles. El propio Anton Kotzig ha calificado el esfuerzo por probar la conjetura como una "enfermedad". [6]
Etiquetado elegante en los bordes
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 con enteros distintos en {1,…, q } de tal manera que el etiquetado de los vértices inducido al etiquetar un vértice con la suma de los bordes incidentes tomada módulo p asigna todos los valores de 0 ap - 1 a los vértices. Se dice que un gráfico G es "elegante en los bordes" si admite un etiquetado elegante en los bordes.
Sheng-Ping Lo introdujo por primera vez las etiquetas de bordes elegantes en 1985. [7]
Una condición necesaria para que un gráfico sea elegante en los bordes es la "condición de Lo":
Etiquetado armonioso
Un "etiquetado armonioso" en un gráfico G es una inyección desde los vértices de G al grupo de 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 la arista para 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 queGráficos de Petersen . Se conjetura que todos los árboles son armoniosos si se permite reutilizar una etiqueta de vértice. [8] El gráfico de libro de siete páginas K 1,7 × K 2 proporciona un ejemplo de un gráfico que no es armonioso. [9]
Coloración gráfica
Una coloración de gráficos es una subclase de etiquetas de gráficos. Los colores de vértice asignan diferentes etiquetas a los vértices adyacentes, mientras que los colores de los bordes asignan diferentes etiquetas a los bordes adyacentes. [10]
Etiquetado afortunado
Un etiquetado suerte de un gráfico G es una asignación de números enteros positivos a los vértices de G tal que si S ( v ) denota la suma de las etiquetas de los vecinos de v , entonces S es un vértice coloración 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 . [11]
Referencias
- ^ a b Weisstein, Eric W. "Gráfico etiquetado" . MathWorld .
- ^ Robert Calderbank, diferentes aspectos de la teoría de la codificación , (1995) ISBN 0-8218-0379-4 , p. 53 "
- ^ " Desarrollos en la teoría del lenguaje ", Proc. Noveno. Conf. Internacional, 2005, ISBN 3-540-26546-5 , pág. 313
- ^ Gallian, J. "Una encuesta dinámica de etiquetado de gráficos, 1996-2005". La Revista Electrónica de Combinatoria. Cite journal requiere
|journal=( ayuda ) - ^ Rosa, Alexander (1967). Sobre determinadas valoraciones de los vértices de un gráfico . Teoría de Gráficos, Int. Symp. Roma, julio de 1966. Gordon y Breach. págs. 349–355. Zbl 0193.53204 .
- ^ Vietri, Andrea (2008). "Navegando hacia, y luego en contra, la conjetura del árbol agraciado: algunos resultados promiscuos". Boletín del Instituto de Combinatoria y sus Aplicaciones . Instituto de Combinatoria y sus Aplicaciones . 53 : 31–46. ISSN 1183-1278 . S2CID 16184248 .
- ^ Lo, Sheng-Ping (1985). "Sobre el borde elegante de las etiquetas de los gráficos". Congressus Numerantium . Conferencia de Sundance, Utah. 50 . págs. 231–241. Zbl 0597.05054 .
- ^ Guy, Richard K. (2004). Problemas no resueltos en teoría de números (3ª ed.). Springer-Verlag . Problema C13, págs. 190-191. ISBN 0-387-20860-7. Zbl 1058.11001 .
- ^ Galiano, Joseph A. (1998). "Una encuesta dinámica de etiquetado de gráficos" . Revista electrónica de combinatoria . 5 : Encuesta dinámica 6. MR 1668059 . .
- ^ Chartrand, Gary ; Egan, Cooroo; Zhang, Ping (2019). Cómo etiquetar un gráfico . SpringerBriefs en Matemáticas. Saltador. págs. 3–4. ISBN 9783030168636.
- ↑ Czerwiński, Sebastian; Grytczuk, Jarosław; Ẓelazny, Wiktor (2009). "Etiquetados afortunados de gráficos". Inf. Proceso. Lett . 109 (18): 1078–1081. doi : 10.1016 / j.ipl.2009.05.011 . Zbl 1197.05125 .
- Extensiones y generalizaciones de gráficos
