Etiquetados Garbosos

y Mágicos en Grafos

El mayor número de métodos de etiquetado de grafos tienen su origen en los conceptos introducidos por Rosa en 1967 o Graham y Sloane en 1980. Rosa, llamó f a una función que era una ß-evaluación de un grafo G con q aristas, donde f era una biyección de los vértices de G a el conjunto {0, 1,..., q} tal que, cuando se le asigna a cada arista xy la etiqueta |f(x)-f(y)|, las etiquetas resultantes son distintas. Posteriormente Golomb llamó a estas etiquetas garbosas ("graceful") y ahora es el término utilizado más popular .

Basándonos en estos conceptos podemos dar una definición aproximada de que es un etiquetado garboso

Podemos decir que hay dos tipos de etiquetados garbosos, el garboso y el garboso "perfecto":

• Etiquetado Garboso

Dado un grafo con n vértices y q aristas, un etiquetado garboso sería aquel en el que se etiqueta a las aristas con los números comprendidos entre 1 y q y los vértices con los números comprendidos entre 0 y q y se tiene que cumplir que las diferencias de las etiquetas de los vértices que delimitan cada arista es el mismo valor de la etiqueta de la arista.

• Etiquetado Garboso Perfecto

Dado un grafo con n vértices y q aristas, un etiquetado garboso perfecto sería aquel en el que se etiqueta a las aristas con los números comprendidos entre 1 y q y los vértices con los números comprendidos entre 1 y n y se tiene que cumplir que las diferencias de las etiquetas de los vértices que delimitan cada arista es el mismo valor de la etiqueta de la arista.

Etiquetados Garbosos en Árboles

• Estrellas

Un grafo estrella es garboso para cualquier número de vértices. El algoritmo para conseguir un etiquetado garboso es muy sencillo. Comenzamos etiquetando el vértice central (este vértice tendrá grado n - 1) con el valor 1. Y a continuación el resto de vértices con 2, 3,..., n. Con esto hemos etiquetado todos los vértices. Nos faltan las aristas y para ello se etiqueta cada arista con la diferencia entre la etiqueta del vértice final y el 1, que es la etiqueta del vértice central. De tal forma que las aristas quedan etiquetadas con los valores 1, 2,..., n-1. Por tanto ya tenemos el etiquetado garboso. En la figura se ve el etiquetado de la estrella mostrada en el caso anterior.

• Caminos

Un camino se denota por Pn y es un tipo de árbol que siempre es garboso.

Si nuestro árbol tiene n vértices y n-1 aristas, empezamos etiquetando por un vértice extremo con los siguientes valores: n, 1, n -1, 2, n -2, 3,..., i, n - i. A continuación etiquetamos las aristas con la diferencia de las etiquetas de los vértices que las limitan. Si empezamos desde la arista conectada al primer vértice extremo, la secuencia será: n-1, n-2,..., 1. Por tanto queda demostrado que todos los caminos son garbosos.

• Orugas

Un grafo oruga es un árbol tal que si se eliminan todos los vértices de grado 1 (finales), el subgrafo resultante es un camino.

G es un grafo oruga y H, el camino creado al borrar todos los vértices finales. n sería el número de vértices de G. Empezamos con uno de los vértices v extremos pertenecientes al camino H, y dividimos los vértices en dos conjuntos X e Y de tal forma que si dos vértices son vecinos, nunca estarán en el mismo conjunto o partición.

Partimos entonces de un vértice v perteneciente a X. Etiquetamos v con el valor n - 1. Etiquetamos los vecinos de v a partir de 0, incrementando en 1 el valor de cada nueva etiqueta y de tal forma que el vecino de v en el camino, w, tenga la etiqueta más alta de todas, entre las etiquetas de los vecinos de v. A continuación, etiquetamos los vecinos de w excepto v con valores descendentes empezando por n - 2, de tal forma que el otro vecino de w en H tenga la etiqueta más pequeña. Se continúa hasta que todos los vértices hayan sido etiquetados.

Los vértices en Y tendrán los valores: 0, 1,..., |Y|-1 y los vértices en X tendrán los valores: n -1, n - 2,..., n - |X|. Este etiquetado de vértices es una biyección que producirá un etiquetado garboso.

Etiquetados Garbosos en Otros Tipos de Grafos

• Ciclo

Un ciclo Cn es garboso si y sólo si n = 0 (mod 4) o n = 3 (mod 4).

1. Si n = 0 (mod 4)



(i - 1)/2 si i es impar

n + 1 - i/2 si i es par y i = n/2

n - i/2 si i es par y i > n/2

1. Si n = 3 (mod 4)



n + 1 - i/2 si i es par

(i - 1)/2 si i es impar y i = (n - 1)/2

(i + 1)/2 si i es impar y i > (n - 1)/2




• Completo

Un grafo completo es un grafo donde cada vértice del grafo es adyacente al resto de grafos y se denota por Kn.

Sólo se admite el etiquetado garboso en grafos completos para n = 2, 3 y 4.

• Bipartito Completo

Un grafo bipartito completo Ka, b siempre es garboso para los enteros a y b.

Algoritmo:

Consideramos dos conjuntos A y B, con a y b vértices, respectivamente. Asignamos a los vértices del conjunto A los números 0, 1, 2,..., a -1, y asignamos a los vértices del conjunto B, las etiquetas a, 2a, 3a,…, ba. De esta forma, todos los enteros de 1 a ab tienen una única aparición como diferencia entre la etiqueta de un vértice del conjunto B y una del conjunto A.

• Rueda

Un grafo rueda es la composición de Cn + K1.

Un grafo rueda siempre es garboso como demostraron R. Frucht en 1979 en su artículo "All Wheels are Graceful" y C. Hoede y H. Kuiper en 1987 en "Graceful Numbering of Wheels and Related Graphs".

La aplicación proporciona solución para n <= 7.

• Grafos de Petersen

Un grafo de Petersen se denota por P(n, k) y se representan para los siguientes valores: para n = 5 y 1 = k = n y es un grafo formado por un conjunto de vértices {a0, a1,..., an-1, b0, b1,..., bn-1} y un conjunto de aristas de la siguiente forma {aiai+1|i = 0, 1,..., n-1}U{ bibi+k|i = 0, 1,..., n-1}U{aibi|i = 0, 1,..., n-1}.

Los grafos de Petersen P(n, k) son garbosos para n = 5, 6, 7, 8, 9 y 10.

• Doble Cono

Un doble cono es resultado del producto cartesiano Cn + K2.

El doble cono Cn + K2 es garboso para n = 3, 4, 5, 7, 8, 9, 11 y 12.



• Producto K4 x Pn

El producto K4 x Pn es garboso para n = 1, 2, 3, 4 y 5. El producto cartesiano se representade la siguiente manera. Ordenamos los 4n vértices de K4 x Pn como sigue {x1,..., x4} (primera copia de k4), {x5,..., x6} (segunda copia de k4),..., {x4n-3,..., x4n} (n copia de k4) y conectamos una a la siguiente por aristas {xixi+4|i = 1, 2,...,4n-4}

Podemos hablar de tres tipos de etiquetados mágicos, aunque aquí nos centraremos en el último. Son:

Dado un grafo conexo G con q aristas, se dice que es semi-mágico si se pueden etiquetar las aristas con enteros de tal forma que para cada vértice v, la suma de las etiquetas de todas las aristas incidentes con v sea la misma para todos los vértices.

Si las etiquetas con las que se etiqueta un grafo son números enteros positivos, todos ellos distintos entre si, estamos hablando de un etiquetado mágico.

Finalmente, si el grafo G, con q aristas, se etiqueta con los números: 1, 2, 3,..., q, de tal forma que se cumpla la condición establecida para un etiquetado semi-mágico, estamos hablando de un etiquetado súper-mágico.

En la literatura de la teoría de grafos, al etiquetado súper-mágico se le conoce como mágico.

En la figura se muestra un ejemplo de un etiquetado mágico.

La aplicación proporciona solución para un tipo de grafos. Concretamente, los grafos bipartitos con exactamente dos ciclos hamiltonianos.

El primer ciclo se etiquetaría con: 4n - 1, 1, 4n - 3, 3,..., 2n + 1, 2n - 1

El segundo ciclo con: 2, 4n, 4, 4n - 2,..., 2n, 2n + 2

Dado un grafo G con n vértices y q aristas, un etiquetado consecutivo sería aquel en el que se etiqueta a los vértices y a las aristas con los números comprendidos entre 1 y n + q. Además debe cumplirse, al igual que en el garboso, que las diferencias de las etiquetas de los vértices que delimitan cada arista es el valor de la etiqueta de la arista.

Para este etiquetado, la aplicación proporciona solución para dos tipos de grafos: estrellas y caminos.

Estrellas

Todas las estrellas tienen un etiquetado consecutivo. El algoritmo del mismo es muy sencillo.

Etiquetamos el vértice central, es decir, el vértice con grado n - 1 con la etiqueta 1. El resto de vértices lo etiquetamos con las etiquetas 3, 5,…, n + q, donde n sería el número de vértices y q el número de aristas. Una vez etiquetados todos los vértices, simplemente tenemos que calcular la etiqueta de cada arista restando el valor de la etiqueta de uno de los vértices que la delimitan del valor del otro vértice. De esta forma todas las etiquetas de vértices y aristas son distintas y además son los números comprendidos entre 1 y n + q.

Camino

No existe ningún algoritmo que resuelva el etiquetado consecutivo de un camino. En la aplicación se ha implementado usando un algoritmo de fuerza bruta.

for all p such that p is already labelled do
     for all q such that q is adjacent to p and q is not yet labelled do
          for all l such that l would be a label for q producing the edge with difference MaxDiff do
               if RecursiveLabel(G) returns a labelling then
                    return the labelling
               else
                    unlabel q
               end if
          end for
     end for
end for

Hasta ahora sólo hemos considerado grafos no dirigidos. Pero para el etiquetado conservativo vamos a centrarnos en los grafos dirigidos. Un grafo dirigido D está formado por un par de conjuntos (V, A) donde V es un conjunto no vacío y A es un (puede ser vacío) conjunto de pares de elementos de V ordenados. En otras palabras, D es un grafo donde cada arista tiene una dirección, normalmente indicada por una flecha. Estas aristas dirigidas suelen llamarse arcos.

Cuando nos hemos referido al etiquetado mágico, al garboso o al consecutivo, la etiqueta se añade a una arista y afecta a los dos extremos de la misma. En el caso del etiquetado conservativo el concepto es diferente. La etiqueta se suma en uno de los lados del arco y se resta en el otro lado, dependiendo de la dirección a la que la flecha apunte. Si la flecha va hacia el vértice, se suma el valor de la etiqueta. Y si apunta al sentido contrario del vértice, se resta.

Basándonos en la ley de Kirchhoff, podemos definir el etiquetado conservativo:

Ley de Kirchhoff. En un grafo dirigido con un etiquetado conservativo, la suma de las etiquetas entrantes es igual a la suma de las etiquetas salientes de cada vértice del grafo.

Hay distintos tipos de grafos que son conservativos, pero la aplicación sólo proporciona solución para las ruedas. El algoritmo para etiquetar una rueda es el siguiente:

Para n impar, las aristas del ciclo se dirigen en el sentido del reloj. Las etiquetas para el ciclo y para las aristas que vienen desde el vértice central vienen indicadas en la figura.

Para n par utilizaremos la figura que se muestra a continuación. La arista con la etiqueta dos está orientada en sentido contrario a las agujas del reloj.

En el ejemplo podemos ver dos grafos rueda dirigidos con el correspondiente etiquetado, siguiendo el algoritmo explicado arriba: