Gráfico doble

El dual de un grafo plano es un grafo en el que los vértices corresponden a las caras del grafo ; dos vértices están conectados por una arista si y solo si las caras correspondientes del gráfico tienen una arista común. Por ejemplo, los gráficos de cubo y octaedro son duales entre sí .

El término dual se usa porque esta propiedad es simétrica: si H es dual con G , entonces G es dual con H (suponiendo que G esté conectado ). La misma noción se puede utilizar para incrustar gráficos en variedades . La noción de dualidad de gráfico es distinta de la dualidad borde-vértice ( gráfico de líneas ) de un gráfico y las dos no deben confundirse.

Propiedades

• El gráfico dual es un seudógrafo : puede tener bucles y múltiples aristas.
• El dual de un gráfico plano es un multigrafo plano .
• Si G es un grafo conexo y si G ′ es el dual de G , entonces G es el dual de G ′.
• Dado que el gráfico dual depende del método de apilamiento , puede haber varios duales (no isomorfos) en el mismo gráfico plano . En la figura, las gráficas rojas no son isomorfas porque la superior tiene grado 6 (cara exterior). Sin embargo, si el gráfico es 3-conexo , como mostró Whitney , el pliegue es único y, por lo tanto, el gráfico dual también es único [1] .

Debido a la dualidad, para cualquier resultado utilizando el número de caras y vértices, estos valores pueden intercambiarse.

Se dice que un grafo es autodual si es isomorfo a su grafo dual. Por ejemplo, el gráfico de tetraedro es autodual .

Dualidad algebraica

Sea G un grafo conexo. Se dice que un gráfico G ★ es algebraicamente dual a un gráfico G tal que G y G ★ tienen el mismo conjunto de aristas, cualquier ciclo en G es un corte de G ★ y cualquier corte de G es un ciclo en G ★ . Cualquier gráfico plano tiene un gráfico dual algebraicamente, que no es único en el caso general (el gráfico dual está determinado por el apilamiento). Lo contrario también es cierto, como mostró Hassler en su criterio de planaridad [2] , un gráfico conexo es plano si y solo si tiene un gráfico dual algebraicamente.

El mismo hecho puede expresarse en términos de la teoría matroide : si M es una matroide gráfica de una gráfica G , entonces la matroide dual M es una matroide gráfica si y sólo si G es plana. Si G es plano, entonces la matroide dual es la matroide gráfica de la gráfica dual de G.

Dualidad débil

Débilmente dual a un gráfico plano es un subgráfico del gráfico dual en el que los vértices corresponden a las caras acotadas del gráfico original. Un grafo plano es plano exterior si y solo si su dual es un bosque , y un grafo plano es un grafo de Halin si y solo si su dual débil es doblemente conexo y plano exterior. Para cualquier gráfico plano G , sea G + un multigrafo plano formado al agregar un solo vértice v a una cara no acotada de G y conectando v a todos los vértices de la cara exterior (varias veces si el vértice aparece varias veces en el límite de la cara). Ahora G es el dual débil del dual (planar) de G + el gráfico [3] [4] .

Notas

1. ↑ Adrián Bondy, USR Murty. capítulo "Grafos planos", Teorema 10.28 // Teoría de grafos. - Springer, 2008. - V. 244. - P. 267. - (Textos de Grado en Matemáticas). — ISBN 9781846289699 . -doi : 10.1007 / 978-1-84628-970-5 .
2. ↑ Hassler Whitney. Gráficos no separables y planos // Transacciones de la Sociedad Matemática Estadounidense. - 1932. - T. 34 , núm. 2 . — S. 339–362 . -doi : 10.1090 / S0002-9947-1932-1501641-2 .
3. ↑ Herbert J. Fleischner, DP Geller, Frank Harary. Gráficos exteriores y duales débiles // Revista de la Sociedad Matemática India. - 1974. - T. 38 . — S. 215–219 .
4. ↑ Maciej M. Sysło, Andrzej Proskurowski. Teoría de grafos: Actas de una conferencia celebrada en Lagów, Polonia, del 10 al 13 de febrero de 1981. - Springer-Verlag, 1983. - Vol. 1018. - P. 248-256. — (Apuntes de clase en Matemáticas). -doi : 10.1007/ BFb0071635 .

Enlaces

• Weisstein, Eric W. Gráfico dual  (inglés) en el sitio web de Wolfram MathWorld .
• Weisstein, Eric W. Gráfico autodual  (inglés) en el sitio web Wolfram MathWorld .