Un grafo etiquetado es la asignación de etiquetas representado mediante enteros, a las aristas o vértices o ambos de un grafo.
El término grafo etiquetado generalmente se refiere a un grafo con vértices etiquetados con todas las etiquetas distintas.
Los grafos puede ser equivalentemente etiquetado mediante enteros consecutivos desde 1 hasta n, donde n es el número de vértices en el grafo.
Para muchas aplicaciones, a las aristas y los vértices le corresponden etiquetas que tienen un significado en el dominio asociado.
Existen 3 tipos de etiquetado:
La figura muestra un etiquetado elegante. Las etiquetas de los vértices están en negro, las etiquetas de las aristas en rojo.
Un grafo es llamado etiquetado 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, las etiquetas de e son la diferencia positiva entre dos vértices incidentes con “e”.
Si “e” es incidente con los vértices etiquetados “k” y “j”, e será etiquetado como ||k - j||. Así un grafo “G”: = (V, E) es elegante si y sólo si existe una inyección que induce una bisección de E a los enteros positivos hasta ||E||.
· 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 modulo “k” que induce una bisecció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”.
· Coloración de grafos
La coloración de grafos es un caso muy especial para los grafos etiquetados, los vértices adyacentes y las aristas coincidentes deben tener diferentes etiquetas.
No hay comentarios:
Publicar un comentario