En la teoría de grafos , la doble cubierta bipartito de un grafo no dirigido G es un bipartito que cubre gráfico de G , con el doble de vértices como G . Puede construirse como el producto tensorial de gráficos , G × K 2 . También se llama la doble cubierta de Kronecker , cubierta doble canónica o simplemente el bipartito doble de G .
No debe confundirse con un ciclo de doble cobertura de un gráfico, una familia de ciclos que incluye cada borde dos veces.
En un gráfico conectado que no es bipartito, solo una cubierta doble es bipartita, pero cuando el gráfico es bipartito o desconectado puede haber más de uno. Por esta razón, Tomaž Pisanski ha argumentado que el nombre "cubierta doble bipartita" debería dejar de utilizarse en favor de los nombres "cubierta doble canónica" o "cubierta Kronecker", que no son ambiguos. [1]
Construcción
La doble cubierta bipartita de G tiene dos vértices u i y w i para cada vértice v i de G . Dos vértices u i y w j están conectados por un borde en la doble cubierta si y sólo si v i y v j están conectados por un borde en G . Por ejemplo, a continuación se muestra una ilustración de una cubierta doble bipartita de un gráfico G no bipartito . 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 cubierta doble se muestran como círculos mientras que los vértices w i se muestran como cuadrados.
La cubierta doble bipartito también puede construirse 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 no nulo de la de dos elementos de grupo .
Ejemplos de
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 cobertura bipartita de la gráfica de un tetraedro , K 4 , es la gráfica de un cubo .
La doble cobertura bipartita de un gráfico de ciclo de longitud impar es un ciclo de dos veces la longitud, mientras que el doble bipartito de cualquier gráfico bipartito (como un ciclo de longitud par, que se muestra en el siguiente ejemplo) está formado por dos copias disjuntas del original. grafico.
Interpretación de matrices
Si un grafo no dirigido G tiene una matriz A como su matriz de adyacencia , entonces la matriz de adyacencia de la doble cobertura de G es
y la matriz biadjacency de la doble cubierta de G es sólo 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 los gráficos dirigidos como matrices de biadyacencia proporciona una equivalencia combinatoria entre los gráficos dirigidos y los gráficos bipartitos equilibrados. [2]
Propiedades
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 . Se conecta una cubierta doble bipartita si y solo si G está conectado y no es bipartito. [3]
La cubierta doble bipartita es un caso especial de una cubierta doble (un gráfico de cubierta doble ). Una doble cobertura en la teoría de grafos puede verse como un caso especial de una 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 forma se pueden obtener varios gráficos cúbicos simétricos conocidos . Por ejemplo, la doble cobertura de K 4 es la gráfica de un cubo; la doble cobertura del gráfico de Petersen es el gráfico de Desargues; y la doble cobertura de la gráfica del dodecaedro es una gráfica cúbica simétrica de 40 vértices. [4]
Es posible que dos gráficos diferentes tengan cubiertas dobles bipartitas isomorfas . Por ejemplo, el gráfico de Desargues no es solo 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. [5] No todos los gráficos bipartitos son una cubierta doble bipartita de otro gráfico; para que un grafo bipartito G sea la cobertura bipartita 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. [5] Por ejemplo, el grafo con dos vértices y un borde es bipartito pero no es una doble cobertura bipartita, porque no tiene pares de vértices no adyacentes que puedan ser mapeados entre sí por tal involución; por otro lado, la gráfica del cubo es una cubierta doble 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 cubierta bipartita .
Otras cubiertas dobles
En general, un gráfico puede tener múltiples cubiertas dobles que son diferentes de la cubierta doble bipartita. [6] En la siguiente figura, el gráfico C es una cubierta doble del gráfico H :
- El gráfico C es un gráfico de cobertura de H : hay un isomorfismo local suprayectivo f de C a H , el indicado por los colores. Por ejemplo, f mapea ambos nodos azules en C al nodo azul en H . Además, sea X la vecindad de un nodo azul en C y sea Y la vecindad del nodo azul en H ; a continuación, la restricción de f a X es una biyección de X a Y . En particular, el grado de cada nodo azul es el mismo. Lo mismo se aplica a cada color.
- El gráfico C es una cubierta doble (o cubierta doble o elevación doble ) de H : la preimagen de cada nodo en H tiene tamaño 2. Por ejemplo, hay exactamente 2 nodos en C que se asignan al nodo azul en H .
Sin embargo, C no es una doble cobertura bipartita de H o cualquier 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 solo uno de ellos es la portada de Kronecker.
Como otro ejemplo, la gráfica del icosaedro es una doble cubierta 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 tapa orientable de un empotramiento de K 6 en el plano proyectivo .
Ver también
Notas
- ^ Pisanski (2018) .
- ^ Dulmage y Mendelsohn (1958) ; Brualdi, Harary y Miller (1980) .
- ^ Brualdi, Harary y Miller (1980) , Teorema 3.4.
- ^ Feng y col. (2008) .
- ↑ a b Imrich y Pisanski (2008) .
- ^ Waller (1976) .
Referencias
- Brualdi, Richard A .; Harary, Frank ; Miller, Zevi (1980), "Bigraphs versus digraphs via matrices", Journal of Graph Theory , 4 (1): 51–73, doi : 10.1002 / jgt.3190040107 , MR 0558453.
- Dulmage, AL; Mendelsohn, NS (1958), "Coberturas de gráficos bipartitos", Canadian Journal of Mathematics , 10 : 517–534, doi : 10.4153 / CJM-1958-052-0 , MR 0097069. Las “cubiertas” en el título de este artículo se refieren al problema de la cubierta de vértice , no a cubiertas dobles bipartitas. Sin embargo, Brualdi, Harary y Miller (1980) citan este artículo como la fuente de la idea de reinterpretar la matriz de adyacencia como una matriz de biadyacencia.
- Feng, Yan-Quan; Kutnar, Klavdija ; Malnič, Aleksander; Marušič, Dragan (2008), "Sobre cubiertas dobles de gráficos", Journal of Combinatorial Theory, Serie B , 98 (2): 324–341, arXiv : math.CO/0701722 , doi : 10.1016 / j.jctb. 2007.07.001 , MR 2389602.
- Imrich, Wilfried; Pisanski, Tomaž (2008), "Gráficos de cobertura de Kronecker múltiple", European Journal of Combinatorics , 29 (5): 1116–1122, arXiv : math / 0505135 , doi : 10.1016 / j.ejc.2007.07.001 , MR 2419215.
- Pisanski, Tomaž (2018), "No todas las cubiertas dobles bipartitas son canónicas", Boletín de la ACI , 82 : 51–55
- Sampathkumar, E. (1975), "On tensor product graphs", Journal of the Australian Mathematical Society , 20 (3): 268–273, doi : 10.1017 / S1446788700020619 , MR 0389681.
- Waller, Derek A. (1976), "Double covers of graphs" (PDF) , Bulletin of the Australian Mathematical Society , 14 (2): 233–248, doi : 10.1017 / S0004972700025053 , hdl : 10338.dmlcz / 101887 , MR 0406876.
enlaces externos
- Weisstein, Eric W. "Gráfico doble bipartito" . MathWorld .