Multigrafo de Shannon

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 25 de diciembre de 2019; las comprobaciones requieren 3 ediciones .

En la teoría de grafos, los multigrafos de Shannon son un tipo especial de gráficos triangulares que se utilizan en el estudio de la coloración de bordes . Withing nombró estos gráficos en honor a Claude Shannon [1] .

Los multigrafos de Shannon son multigrafos de tres vértices que cumplen una de las siguientes condiciones:

a) los tres vértices están conectados por el mismo número de aristas.
b) lo mismo que en a) pero se le añade una arista más.

Más precisamente, un gráfico es un multigrafo de Shannon si tres vértices están conectados por y por aristas, respectivamente . Este multigrafo tiene un grado máximo de . Su multiplicidad (el número máximo de aristas que tienen los mismos extremos) es . ${\ estilo de visualización Sh (n)}$ $\left\lpiso {\frac {n}{2}}\right\rpiso$ $\left\lpiso {\frac {n}{2}}\right\rpiso$ $\left\lpiso {\frac {n+1}{2}}\right\rpiso$ $norte$ $\left\lpiso {\frac {n+1}{2}}\right\rpiso$

Ejemplos

Multigrafos de Shannon
Sh(2)
Sh(3)
Sh(4)
Sh(5)
Sh(6)
Sh(7)

Coloración de bordes

De acuerdo con el teorema de Shannon [2] , cualquier multigrafo con un grado máximo tiene una coloración de borde usando un máximo de colores. Si el número es par, el ejemplo del multigrafo de Shannon con multiplicidad muestra que este límite es exacto: el grado del vértice es exactamente igual, pero cada uno de los bordes está conjugado con cualquier otro borde, por lo que se requieren colores para cualquier borde adecuado colorante. $\Delta$ ${\frac {3}{2}}\Delta$ $\Delta$ ${\ estilo de visualización \ Delta / 2}$ ${\ estilo de visualización \ Delta,}$ ${\frac {3}{2}}\Delta$ ${\frac {3}{2}}\Delta$

Una versión del teorema de Vizing [3] establece que cualquier multigrafo con el máximo grado y multiplicidad se puede colorear utilizando como máximo colores. Nuevamente, este límite es exacto para los multigrafos de Shannon. $\Delta$ $\mu$ ${\ estilo de visualización \ Delta + \ mu}$

Notas

↑ V. G. Vizing. Sobre la estimación de la clase cromática de un p-grafo // Sat. Análisis discreto. - 1964. - T. 3. - S. 25-30.
↑ Claude E. Shannon. Un teorema sobre cómo colorear las líneas de una red // J. Math. Física. - 1949. - T. 28. - S. 148-151.
↑ V. G. Vizing. Clase cromática de un multigrafo // Cibernética. - 1965. - Emisión. 3.- S. 29-39.

Literatura

S. Fiorini, RJ Wilson. Coloraciones de borde de gráficos. - Londres: Pitman, 1977. - V. 16. - P. 34. - (Research Notes in Mathematics). - ISBN 0-273-01129-4 .
Lutz Volkmann. Fundamente der Graphentheorie (neopr.) . - Viena: Springer, 1996. - Pág. 289. - ISBN 3-211-82774-9 .

Enlaces

Lutz Volkmann: Graphen an allen Ecken und Kanten . Apuntes de clase 2006, p. 242 (alemán)