En teoría de grafos , la doble cobertura bipartita de un gráfico no dirigido G es un gráfico de cobertura bipartito de G , con el doble de vértices que G. Puede construirse como el producto tensorial de gráficos , G × K 2 . También se le llama doble cobertura de Kronecker , doble cobertura canónica o simplemente doble bipartita de G.
No debe confundirse con un ciclo de doble cobertura de un gráfico, una familia de ciclos que incluye cada arista dos veces.
La doble cobertura bipartita de G tiene dos vértices u i y w i para cada vértice vi de G . Dos vértices u i y w j están conectados por una arista en la doble cubierta si y sólo si vi y v j están conectados por una arista en G. Por ejemplo, a continuación se muestra una ilustración de una doble cobertura bipartita de un gráfico no bipartito G. En la ilustración, cada vértice del producto tensorial se muestra usando 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 portada se muestran como círculos mientras que los vértices wi se muestran como cuadrados.
La doble cubierta bipartita también se puede construir usando 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 cobertura bipartita del gráfico de Petersen es el gráfico de Desargues : K 2 × G (5,2) = G (10,3) .
La doble cobertura bipartita de un gráfico completo K n es un gráfico de corona (un gráfico bipartito completo K n , n menos una coincidencia perfecta ). En particular, la doble cubierta bipartita de la gráfica de un tetraedro , K 4 , es la gráfica de un cubo .
La doble cubierta bipartita de un gráfico de ciclo de longitud impar es un ciclo de dos veces la longitud, mientras que la doble cubierta 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 original. grafico.
Si un gráfico no dirigido G tiene una matriz A como matriz de adyacencia , entonces la matriz de adyacencia de la doble cobertura de G es
y la matriz de biaadyacencia de la doble cobertura de G es simplemente A en sí. Es decir, la conversión de un gráfico 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 gráficos dirigidos como matrices de biadyacencia proporciona una equivalencia combinatoria entre gráficos dirigidos y gráficos bipartitos equilibrados. [1]
La doble cobertura bipartita de cualquier gráfico G es un gráfico bipartito ; Ambas partes del gráfico bipartito tienen un vértice para cada vértice de G. Una doble cubierta bipartita es conexa si y sólo si G es conexo y no bipartito. [2]
La doble cobertura bipartita es un caso especial de doble cobertura (un gráfico de cobertura doble ). Una doble cobertura en teoría de grafos puede verse como un caso especial de doble cobertura topológica .
Si G es un gráfico simétrico no bipartito , la doble cobertura de G también es un gráfico simétrico; De esta manera se pueden obtener varios gráficos simétricos cúbicos conocidos. Por ejemplo, la doble cubierta de K 4 es la gráfica de un cubo; la doble portada del gráfico de Petersen es el gráfico de Desargues; y la doble cubierta de la gráfica del dodecaedro es una gráfica cúbica simétrica de 40 vértices. [3]
Es posible que dos gráficos diferentes tengan coberturas dobles bipartitas isomorfas . Por ejemplo, el gráfico de Desargues no es sólo la doble cobertura bipartita del gráfico de Petersen, sino que también es la doble cobertura bipartita de un gráfico diferente que no es isomorfo al gráfico de Petersen. [4] No todo grafo bipartito es una doble cobertura bipartita de otro grafo; para que un gráfico bipartito G sea la cobertura bipartita de otro gráfico, es necesario y suficiente que los automorfismos de G incluyan una involución que asigne cada vértice a un vértice distinto y no adyacente. [4] Por ejemplo, el gráfico con dos vértices y una arista es bipartito pero no es una doble cobertura bipartita, porque no tiene pares de vértices no adyacentes que puedan asignarse entre sí mediante dicha involución; por otro lado, la gráfica del cubo es una doble cubierta bipartita y tiene una involución que asigna 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 conexo que no es bipartito sólo una doble cobertura es bipartita, pero cuando el grafo es bipartito o desconectado puede haber más de una. Por esta razón, Tomaž Pisanski ha argumentado que el nombre "doble cobertura bipartita" debería quedar obsoleto en favor de "doble cobertura canónica" o "cobertura de Kronecker", nombres que no son ambiguos. [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 cobertura 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 gráfico resultante tiene cuatro cubiertas dobles distintas. Dos de ellos son bipartitos pero sólo uno de ellos es la portada de Kronecker.
Como otro ejemplo, la gráfica del icosaedro es una doble portada de la gráfica completa K 6 ; Para obtener un mapa de cobertura desde el icosaedro hasta K 6 , asigne cada par de vértices opuestos del icosaedro a un solo vértice de K 6 . Sin embargo, el icosaedro no es bipartito, por lo que no es la doble cubierta bipartita de K 6 . En cambio, se puede obtener como la doble cubierta orientable de una incrustación de K 6 en el plano proyectivo .
Las dobles portadas de un gráfico corresponden a las diferentes formas de firmar las aristas del gráfico.
![{\displaystyle \left[{\begin{matrix}0&A\\A^{T}&0\end{matrix}}\right],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0b04896754d39fbfcb50519550c82e74d77be67a)