En teoría de grafos , la doble cobertura bipartita de un grafo no dirigido G es un grafo bipartito envolvente de G , con el doble de vértices que G. Puede construirse como el producto tensorial de grafos , G × K 2 . También se denomina doble cobertura de Kronecker , doble cobertura canónica o simplemente doble bipartito de G.
No debe confundirse con un ciclo de doble cobertura de un grafo, una familia de ciclos que incluye cada arista dos veces.
La doble cubierta bipartita de G tiene dos vértices u i y w i por cada vértice v i de G . Dos vértices u i y w j están conectados por una arista en la doble cubierta si y solo si v i y v j están conectados por una arista en G . Por ejemplo, a continuación se muestra una ilustración de una doble cubierta bipartita de un grafo no bipartito G . En la ilustración, cada vértice en el producto tensorial se muestra utilizando un color del primer término del producto ( G ) y una forma del segundo término del producto ( K 2 ); por lo tanto, los vértices u i en la doble cubierta se muestran como círculos mientras que los vértices w i se muestran como cuadrados.
La doble cubierta bipartita también puede construirse utilizando matrices de adyacencia (como se describe a continuación) o como el gráfico derivado de un gráfico de voltaje en el que cada borde de G está etiquetado por el elemento distinto de cero del grupo de dos elementos .
La doble cubierta bipartita del grafo de Petersen es el grafo de Desargues : K 2 × G (5,2) = G (10,3) .
La doble cubierta bipartita de un grafo completo K n es un grafo corona (un grafo bipartito completo K n , n menos un emparejamiento perfecto ). En particular, la doble cubierta bipartita del grafo de un tetraedro , K 4 , es el grafo de un cubo .
La doble cubierta bipartita de un gráfico de ciclo de longitud impar es un ciclo del doble de longitud, mientras que la doble bipartita de cualquier gráfico bipartito (como un ciclo de longitud par, que se muestra en el siguiente ejemplo) está formada por dos copias disjuntas del gráfico original.
Si un grafo no dirigido G tiene una matriz A como su matriz de adyacencia , entonces la matriz de adyacencia de la doble cubierta de G es
y la matriz de biadyacencia de la doble cobertura de G es simplemente A en sí misma. Es decir, la conversión de un grafo a su doble cobertura se puede realizar simplemente reinterpretando A como una matriz de biadyacencia en lugar de como una matriz de adyacencia. De manera más general, la reinterpretación de las matrices de adyacencia de grafos dirigidos como matrices de biadyacencia proporciona una equivalencia combinatoria entre grafos dirigidos y grafos bipartitos balanceados. [1]
La doble cubierta bipartita de cualquier grafo G es un grafo bipartito ; ambas partes del grafo bipartito tienen un vértice por cada vértice de G. Una doble cubierta bipartita es conexa si y solo si G es conexo y no bipartito. [2]
La doble cobertura bipartita es un caso especial de una doble cobertura (un grafo de cobertura doble ). Una doble cobertura en teoría de grafos puede considerarse como un caso especial de una doble cobertura topológica .
Si G es un grafo simétrico no bipartito , la doble cobertura de G es también un grafo simétrico; de esta manera se pueden obtener varios grafos cúbicos simétricos conocidos. Por ejemplo, la doble cobertura de K 4 es el grafo de un cubo; la doble cobertura del grafo de Petersen es el grafo de Desargues; y la doble cobertura del grafo del dodecaedro es un grafo cúbico simétrico de 40 vértices. [3]
Es posible que dos grafos diferentes tengan dobles recubrimientos bipartitos isomorfos . Por ejemplo, el grafo de Desargues no es solo el doble recubrimiento bipartito del grafo de Petersen, sino que también es el doble recubrimiento bipartito de un grafo diferente que no es isomorfo al grafo de Petersen. [4] No todo grafo bipartito es un doble recubrimiento bipartito de otro grafo; para que un grafo bipartito G sea el recubrimiento bipartito de otro grafo, es necesario y suficiente que los automorfismos de G incluyan una involución que mapee cada vértice a un vértice distinto y no adyacente. [4] Por ejemplo, el grafo con dos vértices y una arista es bipartito pero no es un doble recubrimiento bipartito, porque no tiene pares de vértices no adyacentes que se mapeen entre sí mediante tal involución; por otro lado, el grafo del cubo es un doble recubrimiento bipartito y tiene una involución que mapea cada vértice al vértice diametralmente opuesto. Sampathkumar (1975) obtuvo una caracterización alternativa de los gráficos bipartitos que pueden formarse mediante la construcción de doble cobertura bipartita.
En un grafo conectado que no es bipartito, sólo una doble cobertura es bipartita, pero cuando el grafo es bipartito o no está conectado puede haber más de una. Por esta razón, Tomaž Pisanski ha argumentado que el nombre "doble cobertura bipartita" debería ser desaprobado en favor de "doble cobertura canónica" o "cobertura de Kronecker", nombres que son inequívocos. [5]
En general, un gráfico puede tener múltiples coberturas dobles que son diferentes de la cobertura doble bipartita. [6]
En la siguiente figura, el gráfico C es una doble cobertura del gráfico H :
Sin embargo, C no es la doble cubierta bipartita de H ni de ningún otro gráfico; no es un gráfico bipartito.
Si reemplazamos un triángulo por un cuadrado en H, el grafo resultante tiene cuatro coberturas dobles distintas. Dos de ellas son bipartitas, pero sólo una de ellas es la cobertura de Kronecker.
Como otro ejemplo, el grafo del icosaedro es una doble cobertura del grafo completo K 6 ; para obtener una función de cobertura del icosaedro a K 6 , mapee cada par de vértices opuestos del icosaedro a un único vértice de K 6 . Sin embargo, el icosaedro no es bipartito, por lo que no es la doble cobertura bipartita de K 6 . En cambio, se puede obtener como la doble cobertura orientable de una incrustación de K 6 en el plano proyectivo .
Las dobles tapas de un gráfico corresponden a las diferentes formas de firmar las aristas del gráfico.
![{\displaystyle \left[{\begin{matriz}0&A\\A^{T}&0\end{matriz}}\right],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0b04896754d39fbfcb50519550c82e74d77be67a)