Gráfico de voltaje

En teoría de grafos , un grafo de voltaje es un grafo dirigido cuyas aristas están etiquetadas de forma invertible mediante elementos de un grupo . Formalmente es idéntico a un grafo de ganancia , pero en teoría topológica de grafos se utiliza generalmente como una forma concisa de especificar otro grafo, denominado grafo derivado del grafo de voltaje.

Las opciones típicas de los grupos utilizados para gráficos de voltaje incluyen el grupo de dos elementos.${\displaystyle \mathbb {Z} _ {2}}$(para definir la doble cubierta bipartita de un grafo), grupos libres (para definir la cubierta universal de un grafo), retículos enteros d -dimensionales${\displaystyle \mathbb {Z} ^{d}}$(considerado 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${\displaystyle \mathbb {Z_ {n}}}$para n > 2. Cuando Π es un grupo cíclico, el gráfico de voltaje puede llamarse gráfico de voltaje cíclico .  

Definición formal de un gráfico de tensión Π , para un grupo Π dado :

• Comience con un dígrafo G. (La dirección es únicamente para facilitar la notación).
• Un voltaje Π en un arco de G es una etiqueta del arco por un elemento.${\displaystyle x\in \Pi }$. Por ejemplo, en el caso donde${\displaystyle \Pi =\mathbb {Z} _ {n}}$, la etiqueta es un número i  (mod n ). 
• Una asignación de voltaje Π es una función${\displaystyle \alpha :E(G)\rightarrow \Pi }$que etiqueta cada arco de G con un voltaje Π.
• Un gráfico de voltaje Π es un par${\displaystyle (G,\alpha:E(G)\rightarrow \Pi)}$de tal manera que G es un digrafo y α es una asignación de voltaje.
• El grupo de voltaje de un gráfico de voltaje${\displaystyle (G,\alpha:E(G)\rightarrow \Pi)}$es el grupo Π del cual se asignan los voltajes.

Cabe señalar que los voltajes de un grafo de voltajes no necesariamente satisfacen la ley de voltajes de Kirchhoff , que establece que la suma de los voltajes alrededor de un camino cerrado es cero (el elemento neutro del grupo), aunque esta ley sí se cumple para los grafos derivados que se describen a continuación. Por lo tanto, el nombre puede resultar algo engañoso. Proviene del origen de los grafos de voltajes como duales a los grafos de corrientes de la teoría topológica de grafos .

La gráfica derivada de una gráfica de voltaje${\displaystyle (G,\alpha :E(G)\rightarrow \mathbb {Z} _{n})}$es el gráfico${\displaystyle {\tilde {G}}}$cuyo conjunto de vértices es${\displaystyle {\tilde {V}}=V\times \mathbb {Z} _ {n}}$y cuyo conjunto de aristas es${\displaystyle {\tilde {E}}=E\times \mathbb {Z} _{n}}$donde los extremos de una arista ( e , k ) tales que e tiene cola v y cabeza w son${\displaystyle (v,\ k)}$y${\displaystyle (w,\ k+\alpha (e))}$.

Aunque los grafos de voltaje se definen para digrafos, pueden extenderse a grafos no dirigidos reemplazando cada arista no dirigida por un par de aristas dirigidas de orden opuesto y exigiendo que estas aristas tengan etiquetas inversas entre sí en la estructura de grupo. En este caso, el grafo resultante también tendrá la propiedad de que sus aristas dirigidas forman pares de aristas de orientación opuesta, por lo que el propio grafo resultante puede interpretarse como un grafo no dirigido.

El grafo derivado es un grafo de recubrimiento del grafo de voltaje dado. Si ninguna etiqueta de arista del grafo de voltaje es el elemento identidad, entonces los elementos del grupo asociados con los vértices del grafo derivado proporcionan una coloración del grafo derivado con un número de colores igual al orden del grupo. Un caso especial importante es el recubrimiento doble bipartito , el grafo derivado de un grafo de voltaje en el que todas las aristas están etiquetadas con el elemento distinto de la identidad de un grupo de dos elementos. Debido a que el orden del grupo es dos, el grafo derivado en este caso tiene garantizado ser bipartito .

Se conocen algoritmos de tiempo polinomial para determinar si el gráfico derivado de un${\displaystyle \mathbb {Z} ^{d}}$-El gráfico de voltaje contiene cualquier ciclo dirigido. ^{[ 1 ]}

Cualquier grafo de Cayley de un grupo Π , con un conjunto dado Γ de generadores, puede definirse como el grafo derivado para un grafo de Π -voltaje que tiene un vértice y Γ bucles, cada uno etiquetado con uno de los generadores en Γ . ^{[ 2 ]}

El gráfico de Petersen es el gráfico derivado para un${\displaystyle \mathbb {Z} _ {5}}$-grafo de voltaje en forma de mancuerna con dos vértices y tres aristas: una arista que conecta los dos vértices y un bucle en cada vértice. Un bucle se etiqueta con 1, el otro con 2, y la arista que conecta los dos vértices se etiqueta con 0. De manera más general, la misma construcción permite construir cualquier grafo de Petersen generalizado GP( n , k ) como un grafo derivado del mismo grafo de mancuerna con etiquetas 1, 0 y k en el grupo${\displaystyle \mathbb {Z} _ {n}}$. ^{[ 3 ]}

Los vértices y aristas de cualquier teselación periódica del plano pueden formarse como el grafo derivado de un grafo finito, con voltajes en${\displaystyle \mathbb {Z} ^{2}}$.

• Cohen, Edith ; Megiddo, Nimrod (1989), "Algoritmos fuertemente polinomiales y NC para la detección de ciclos en grafos dinámicos", Actas del 21.º Simposio Anual de la ACM sobre Teoría de la Computación (STOC '89) , págs. 523-534 , doi : 10.1145/73007.73057 , ISBN  0-89791-307-8.
• Gross, Jonathan L. (1974), "Gráficas 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 grafos 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), Teoría topológica de grafos , Nueva York: Wiley.
• Iwano, K.; Steiglitz, K. (1987), "Prueba de ciclos en grafos infinitos con estructura periódica", Actas del 19.º Simposio Anual de la ACM sobre Teoría de la Computación (STOC '87) , págs. 46-55 , doi : 10.1145/28395.28401 , ISBN  0-89791-221-7, S2CID 37934099 .
• Kosaraju, S. Rao ; Sullivan, Gregory (1988), "Detección de ciclos en grafos dinámicos en tiempo polinomial", Actas del 20.º Simposio Anual de la ACM sobre Teoría de la Computación (STOC '88) , págs. 398–406 , doi : 10.1145/62212.62251 , ISBN  0-89791-264-0, S2CID 14290312 .