En la teoría de grafos , un gráfico de voltaje es un gráfico dirigido cuyos bordes están etiquetados de forma invertida por elementos de un grupo . Es formalmente idéntico a un gráfico de ganancia , pero generalmente se usa en la teoría de gráficos topológicos como una forma concisa de especificar otro gráfico llamado gráfico derivado del gráfico de voltaje.
Las opciones típicas de los grupos utilizados para los gráficos de voltaje incluyen el grupo de dos elementos ℤ 2 (para definir la doble cobertura bipartita de un gráfico), grupos libres (para definir la cobertura universal de un gráfico), rejillas enteras d- dimensionales ℤ d ( visto como un grupo bajo la suma de vectores, para definir estructuras periódicas en el espacio euclidiano d- dimensional ), [1] y grupos cíclicos finitos ℤ n para n > 2. Cuando Π es un grupo cíclico, el gráfico de voltaje puede llamarse cíclico- gráfico de voltaje.
Definición
Definición formal de un gráfico de voltaje Π , para un grupo dado Π :
- Comenzar con un dígrafo G . (La dirección es únicamente por conveniencia en la notación).
- Un Π -voltaje en un arco de G es una etiqueta del arco por un elemento x de Π . Por ejemplo, en el caso donde Π = ℤ n , la etiqueta es un número i (mod n ).
- Una asignación de tensión Π es una funciónque etiqueta cada arco de G con un voltaje Π.
- Un gráfico de Π -voltaje es un partal que G es un dígrafo y α es una asignación de voltaje.
- El grupo de voltaje de un gráfico de voltajees el grupo Π a partir del cual se asignan las tensiones.
Tenga en cuenta que los voltajes de un gráfico de voltaje no necesitan satisfacer la ley de voltaje de Kirchhoff , que la suma de voltajes alrededor de un camino cerrado es 0 (el elemento de identidad del grupo), aunque esta ley se cumple para los gráficos derivados que se describen a continuación. Por tanto, el nombre puede resultar algo engañoso. Es el resultado del origen de los gráficos de voltaje como dual a los gráficos actuales de la teoría de gráficos topológicos .
El gráfico derivado
El gráfico derivado de un gráfico de voltaje es el grafico cuyo conjunto de vértices es y cuyo borde es , donde los extremos de una arista ( e , k ) tal que e tiene cola v y cabeza w son y .
Aunque los gráficos de voltaje se definen para los dígrafos, pueden extenderse a gráficos no dirigidos reemplazando cada borde no dirigido por un par de bordes dirigidos ordenados de manera opuesta y requiriendo que estos bordes tengan etiquetas que sean inversas entre sí en la estructura del grupo. En este caso, el gráfico derivado también tendrá la propiedad de que sus bordes dirigidos forman pares de bordes orientados de manera opuesta, por lo que el gráfico derivado puede interpretarse como un gráfico no dirigido.
El gráfico derivado es un gráfico de cobertura del gráfico de voltaje dado. Si ninguna etiqueta de borde del gráfico de voltaje es el elemento de identidad, entonces los elementos de grupo asociados con los vértices del gráfico derivado proporcionan una coloración del gráfico derivado con un número de colores igual al orden del grupo. Un caso especial importante es la doble cobertura bipartita , el gráfico derivado de un gráfico de voltaje en el que todos los bordes están etiquetados con el elemento no identitario de un grupo de dos elementos. Debido a que el orden del grupo es dos, se garantiza que el gráfico derivado en este caso será bipartito .
Los algoritmos de tiempo polinomial son conocidos por determinar si el gráfico derivado de un-El gráfico de voltaje contiene los ciclos dirigidos. [1]
Ejemplos de
Cualquier gráfico de Cayley de un grupo Π , con un conjunto Γ dado de generadores, puede definirse como el gráfico derivado de un gráfico de Π- voltaje que tiene un vértice y | Γ | bucles automáticos, cada uno etiquetado con uno de los generadores en Γ . [2]
El gráfico de Petersen es el gráfico derivado de un gráfico de voltaje de ℤ 5 en forma de mancuerna con dos vértices y tres bordes: un borde que conecta los dos vértices y un bucle automático en cada vértice. Un auto-bucle está etiquetado con 1, el otro con 2, y el borde que conecta los dos vértices está etiquetado como 0. De manera más general, la misma construcción permite que cualquier gráfico de Petersen generalizado GP ( n , k ) se construya como un gráfico derivado de el mismo gráfico con mancuernas con etiquetas 1, 0 y k en el grupo ℤ n . [3]
Los vértices y aristas de cualquier teselación periódica del plano pueden formarse como el gráfico derivado de un gráfico finito, con voltajes en ℤ 2 .
Notas
- ↑ a b Iwano y Steiglitz (1987) ; Kosaraju y Sullivan (1988) ; Cohen y Megiddo (1989) .
- ^ Gross y Tucker (1987) , Teorema 2.2.3, p. 69.
- ^ Gross y Tucker (1987) , ejemplo 2.1.2, p.58.
Referencias
- Cohen, Edith ; Megiddo, Nimrod (1989), "Algoritmos fuertemente polinomiales y NC para la detección de ciclos en gráficos dinámicos", Proc. 21º Simposio Anual de ACM sobre Teoría de la Computación (STOC '89) , págs. 523–534, doi : 10.1145 / 73007.73057.
- Gross, Jonathan L. (1974), "Gráficos de voltaje", Matemáticas discretas , 9 (3): 239–246, doi : 10.1016 / 0012-365X (74) 90006-5.
- Gross, Jonathan L .; Tucker, Thomas W. (1977), "Generación de todas las coberturas de gráficos mediante asignaciones de voltaje de permutación", Matemáticas discretas , 18 (3): 273-283, doi : 10.1016 / 0012-365X (77) 90131-5.
- Gross, Jonathan L .; Tucker, Thomas W. (1987), Topological Graph Theory , Nueva York: Wiley.
- Iwano, K .; Steiglitz, K. (1987), "Prueba de ciclos en gráficas infinitas con estructura periódica", Proc. XIX Simposio anual de ACM sobre teoría de la computación (STOC '87) , págs. 46–55, doi : 10.1145 / 28395.28401.
- Kosaraju, S. Rao ; Sullivan, Gregory (1988), "Detección de ciclos en gráficos dinámicos en tiempo polinomial", Proc. 20o Simposio anual de ACM sobre teoría de la computación (STOC '88) , págs. 398–406, doi : 10.1145 / 62212.62251.