En la disciplina matemática de la teoría de gráfico, un gráfico del que etiqueta es la asignación de los números enteros a los bordes o a las cimas, o ambas, gráfico . La estrategia de etiquetado depende de la categoría del etiquetado.

Definición

Dado un $G\; del\; gráfico:\; =\; (V,\; E)$ tales que $V$ es el sistema de cimas y $E$ es el sistema de bordes, una cima del que etiqueta es una función de un cierto subconjunto de los números enteros a los verticies del gráfico. Asimismo, un borde del que etiqueta es una función de un cierto subconjunto de los números enteros a los bordes del gráfico.

Historia

La mayoría de los labelings del gráfico remontan sus orígenes a los labelings presentados por Alex Rosa en su papel 1967. Rosa identificó tres tipos de labelings, que él llamó el α-, el β-, y los ρ-labelings. los β-Labelings más adelante fueron retitulados el agraciado por S. Golomb y el nombre ha sido popular desde entonces.

Etiquetado agraciado

Un gráfico se conoce como agraciado cuando sus cimas se etiquetan a partir de la 0 al $\backslash |E\; \backslash |$, el tamaño del gráfico, y éste que etiqueta induce un borde que etiqueta a partir de la 1 al $\backslash |E\; \backslash |$. Para cualquier borde $e$, la etiqueta de $e$ es la diferencia positiva entre el incidente de dos cimas con el E. es decir si $e$ es incidente con las cimas etiquetadas $k$ y $j$, $e$ será etiquetada $\backslash |k\; -\; j\; \backslash |$. Así, un $G\; del\; gráfico:\; =\; (V,\; E)$ es agraciado si y solamente si existe una inyección que induzca un bijection de $E$ a los números enteros positivos hasta $\backslash |E\; \backslash |$.

En su papel original, Rosa probó que todos los gráficos eulerianos con el equivalente de la orden a 1 o a 2 (la MOD 4) no es agraciada. Independientemente de si ciertas familias de gráficos son agraciadas es un área de la teoría de gráfico debajo de extenso estudia. Discutible, la conjetura sin probar más grande del etiquetado del gráfico es la conjetura de Ringel-Kotzig, que presume que todos los árboles son agraciados. Esto se ha probado para todas las trayectorias, las orugas, y muchas otras familias infinitas de árboles. Kotzig mismo ha llamado el esfuerzo para probar la conjetura un " disease."

Labelings armoniosos

considera también:

etiquetado Borde-agraciado Un gráfico armonioso es un gráfico con los bordes de k que permite una inyección del cimas de G al grupo de Modulo k de los números enteros que induce un bijection entre los bordes de $G$ y los números enteros positivos hasta $\backslash |E\; \backslash |$. Para cualquier borde $e$, la etiqueta de $e$ es la suma de las etiquetas del incidente de dos cimas con $e$ (MOD q).