Marcado gráfico

El etiquetado de gráficos en matemáticas  es la asignación de etiquetas, que tradicionalmente se representan mediante números enteros , aristas , vértices o aristas y vértices de un gráfico [1] .

Formalmente, dado un gráfico G = ( V , E ) , una etiqueta de vértice es una función del conjunto de vértices V al conjunto de etiquetas . Una gráfica con tal función se llama gráfica etiquetada con vértice . De manera similar, el etiquetado de los bordes es una función del conjunto de bordes E al conjunto de etiquetas. En este caso, el gráfico se denomina gráfico con borde etiquetado .

En el caso de que las etiquetas de borde sean elementos de un conjunto ordenado (es decir, números reales ), el etiquetado puede llamarse gráfico ponderado .

A menos que se indique explícitamente, el término etiquetado de gráficos generalmente significa etiquetado de vértices donde todas las etiquetas son distintas. Tal gráfico se puede etiquetar de manera equivalente con 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 tienen sentido en el área correspondiente. Por ejemplo, a los bordes se les pueden asignar pesos que representan el "costo" del viaje entre dos vértices adyacentes [2] .

En la definición anterior, un grafo se entiende como un grafo simple no dirigido finito. Sin embargo, la noción de marcado se aplica a todas las extensiones y generalizaciones de grafos. Por ejemplo, en la teoría de autómatas y la teoría de lenguajes formales , se suelen considerar multigrafos etiquetados , es decir, grafos en los que un par de vértices pueden estar conectados por varias aristas etiquetadas [3] .

Historia

La mayoría de las etiquetas de gráficos tienen su origen en las etiquetas introducidas por Alex Rosa en su artículo de 1967 [4] . Rosa identificó tres tipos de etiquetado, a los que llamó etiquetas α, β y ρ [5] . El marcado β fue renombrado más tarde por S. V. Golomb como agraciado y este nombre se hizo popular.

Ocasiones especiales

Marcado elegante

Un gráfico se llama elegante si sus vértices están etiquetados con números del 0 al | E |, el tamaño del gráfico, y este etiquetado genera un etiquetado de borde de 1 a | E |. Para cualquier arista e , la etiqueta de la arista e es igual a la diferencia positiva entre los dos vértices de la arista e . En otras palabras, si la arista e incide en dos vértices rotulados i y j , entonces la arista e está rotulada | yo − j |. Por lo tanto, un gráfico G = ( V , E ) es elegante si y solo si hay una incrustación que genera una biyección de E en números enteros positivos hasta | E |.

En su trabajo, Rosa demostró que todos los ciclos de Euler de tamaño comparable a 1 o 2 ( módulo 4) no son elegantes. Actualmente se está investigando intensamente qué familias de gráficos son elegantes. Quizás la mayor conjetura no probada en el etiquetado de gráficos es la conjetura de Ringel-Kotzig, que establece que todos los árboles son elegantes. Esto ha sido probado para todos los caminos , orugas , y muchas otras infinitas familias de árboles. El mismo Kotzig llamó al intento de probar la conjetura "malvado" [6] .

Marcas agraciadas con bordes

El etiquetado elegante de aristas de gráficos simples (gráficos sin bucles y aristas múltiples) con p vértices y q aristas es el etiquetado de aristas por diferentes enteros del conjunto {1, ..., q }, tal que el etiquetado de vértices generado por el etiquetado de vértices como la suma de las aristas adyacentes sobre el módulo p , que asigna todos los valores de 0 a p − 1 a los vértices. Se dice que un grafo G es elegante en los bordes si permite un etiquetado elegante en los bordes.

El marcado elegante de las costillas fue el primero en ser introducido por S. Lo en 1985 [7] .

Una condición necesaria para la existencia de un etiquetado elegante de borde para un gráfico es la condición Lo :

Marcado armonioso

Un etiquetado armónico de un grafo G es una incrustación del conjunto de vértices de un grafo G en un grupo de enteros de congruencia módulo k , donde k es el número de aristas del grafo G , lo que genera una biyección entre las aristas del grafo Grafique G y los números módulo k eligiendo las sumas de las etiquetas de dos vértices x , y (mod k ) de los bordes ( x , y ). Un gráfico armónico es un gráfico que tiene un etiquetado armonioso. Los ciclos impares son gráficos armónicos, como lo es el gráfico de Petersen . Existe la conjetura de que todos los árboles son gráficos armónicos si se permite reutilizar un vértice [8] . El libro de siete páginas K 1.7 × K 2 da un ejemplo de un gráfico no armónico [9] .

Colorear gráficos

La coloración de gráficos es una subclase del marcado de gráficos. La coloración de vértices asigna diferentes etiquetas a los vértices adyacentes, la coloración de bordes asigna diferentes etiquetas a los bordes adyacentes.

Marcado de la suerte

Un etiquetado afortunado de G es la asignación de enteros positivos a los vértices de G de tal manera que si S ( v ) es la suma de las etiquetas de los vértices vecinos de v , entonces S es la coloración de vértice de G . El número de la suerte de un gráfico G es el menor k que el gráfico G tiene un etiquetado afortunado con números enteros {1, …, k } [10] .

Notas

  1. ↑ 1 2 Weisstein, Eric W. Gráfico etiquetado  (inglés) en el sitio web de Wolfram MathWorld .
  2. ↑ Calderbank, 1995 , pág. 53.
  3. ↑ Desarrollos en la teoría del lenguaje, 2005 .
  4. ↑ Gallian, 1998 .
  5. ↑ Rosa .
  6. ↑ Vietri, 2008 , pág. 31–46.
  7. ↑ Lo, 1985 , pág. 231–241.
  8. ↑ Guy, 2004 , pág. 190–191.
  9. ↑ Gallian, 1998 , p. Encuesta Dinámica 6.
  10. ↑ Czerwiński, Grytczuk, Ẓelazny, 2009 , p. 1078-1081.

Literatura