En la disciplina matemática de la teoría de grafos , el grafo dual de un grafo plano G es un grafo que tiene un vértice para cada cara de G. El grafo dual tiene una arista para cada par de caras en G que están separadas entre sí por una arista, y un bucle propio cuando la misma cara aparece en ambos lados de una arista. Por lo tanto, cada arista e de G tiene una arista dual correspondiente, cuyos puntos finales son los vértices duales correspondientes a las caras a cada lado de e . La definición del dual depende de la elección de la incrustación del grafo G , por lo que es una propiedad de los grafos planos (grafos que ya están incrustados en el plano) en lugar de los grafos planos (grafos que pueden estar incrustados pero para los cuales la incrustación aún no se conoce). Para los grafos planos en general, puede haber múltiples grafos duales, dependiendo de la elección de la incrustación plana del grafo.
Históricamente, la primera forma de dualidad de grafos que se reconoció fue la asociación de los sólidos platónicos en pares de poliedros duales . La dualidad de grafos es una generalización topológica de los conceptos geométricos de poliedros duales y teselaciones duales , y a su vez se generaliza combinatoriamente mediante el concepto de matroide dual . Las variaciones de la dualidad de grafos planos incluyen una versión de dualidad para grafos dirigidos y dualidad para grafos incrustados en superficies bidimensionales no planas.
Estas nociones de gráficos duales no deben confundirse con una noción diferente, el dual de arista a vértice o gráfico lineal de un gráfico.
El término dual se utiliza porque la propiedad de ser un grafo dual es simétrica , lo que significa que si H es dual de un grafo conexo G , entonces G es dual de H. Cuando se habla del dual de un grafo G , el grafo G en sí mismo puede denominarse "grafo primario". Muchas otras propiedades y estructuras de grafos pueden traducirse en otras propiedades y estructuras naturales del dual. Por ejemplo, los ciclos son duales a los cortes , los árboles de expansión son duales a los complementos de los árboles de expansión y los grafos simples (sin aristas paralelas ni bucles propios ) son duales a los grafos conexos de 3 aristas .
La dualidad de grafos puede ayudar a explicar la estructura de los laberintos y de las cuencas de drenaje . Los grafos duales también se han aplicado en la visión artificial , la geometría computacional , la generación de mallas y el diseño de circuitos integrados .
La incrustación planar única de un gráfico de ciclo divide el plano en solo dos regiones, el interior y el exterior del ciclo, por el teorema de la curva de Jordan . Sin embargo, en un n -ciclo, estas dos regiones están separadas entre sí por n aristas diferentes. Por lo tanto, el gráfico dual del n -ciclo es un multigrafo con dos vértices (duales a las regiones), conectados entre sí por n aristas duales. Un gráfico de este tipo se denomina arista múltiple, enlace o, a veces, grafo dipolar . Por el contrario, el dual a un grafo dipolar de n aristas es un n -ciclo. [1]
Según el teorema de Steinitz , todo grafo poliédrico (el grafo formado por los vértices y las aristas de un poliedro convexo tridimensional ) debe ser plano y conexo por 3 vértices , y todo grafo plano conexo por 3 vértices proviene de un poliedro convexo de esta manera. Todo poliedro convexo tridimensional tiene un poliedro dual ; el poliedro dual tiene un vértice por cada cara del poliedro original, con dos vértices duales adyacentes siempre que las dos caras correspondientes compartan una arista. Siempre que dos poliedros sean duales, sus grafos también lo serán. Por ejemplo, los sólidos platónicos vienen en pares duales, con el octaedro dual al cubo, el dodecaedro dual al icosaedro y el tetraedro dual a sí mismo. [2] La dualidad de poliedros también puede extenderse a la dualidad de politopos de dimensiones superiores , [3] pero esta extensión de la dualidad geométrica no tiene conexiones claras con la dualidad de teoría de grafos.
Se dice que un grafo plano es autodual si es isomorfo a su grafo dual. Los grafos en rueda proporcionan una familia infinita de grafos autoduales que provienen de poliedros autoduales (las pirámides ). [4] [5] Sin embargo, también existen grafos autoduales que no son poliédricos, como el que se muestra. Servatius y Christopher (1992) describen dos operaciones, adhesión y explosión, que se pueden utilizar para construir un grafo autodual que contenga un grafo plano dado; por ejemplo, el grafo autodual que se muestra se puede construir como la adhesión de un tetraedro con su dual. [5]
De la fórmula de Euler se desprende que todo grafo autodual con n vértices tiene exactamente 2 n − 2 aristas. [6] Todo grafo planar autodual simple contiene al menos cuatro vértices de grado tres, y cada incrustación autodual tiene al menos cuatro caras triangulares. [7]
Muchos conceptos naturales e importantes en la teoría de grafos corresponden a otros conceptos igualmente naturales pero diferentes en el grafo dual. Debido a que el dual del dual de un grafo plano conexo es isomorfo al grafo primal, [8] cada uno de estos emparejamientos es bidireccional: si el concepto X en un grafo plano corresponde al concepto Y en el grafo dual, entonces el concepto Y en un grafo plano corresponde al concepto X en el dual.
El dual de un grafo simple no necesita ser simple: puede tener bucles propios (una arista con ambos puntos finales en el mismo vértice) o múltiples aristas que conectan los mismos dos vértices, como ya fue evidente en el ejemplo de multigrafos dipolares que son duales a grafos de ciclo. Como un caso especial de la dualidad de corte-ciclo discutida más adelante, los puentes de un grafo planar G están en correspondencia uno a uno con los bucles propios del grafo dual. [9] Por la misma razón, un par de aristas paralelas en un multigrafo dual (es decir, un ciclo de longitud 2) corresponde a un conjunto de corte de 2 aristas en el grafo primal (un par de aristas cuya eliminación desconecta el grafo). Por lo tanto, un grafo planar es simple si y solo si su dual no tiene conjuntos de corte de 1 o 2 aristas; es decir, si es conexo por 3 aristas . Los grafos planares simples cuyos duales son simples son exactamente los grafos planares simples conexos por 3 aristas. [10] Esta clase de grafos incluye, pero no es la misma que, la clase de grafos planos simples conexos por 3 vértices . Por ejemplo, la figura que muestra un grafo autodual es conexo por 3 aristas (y por lo tanto su dual es simple) pero no es conexo por 3 vértices.
Como el grafo dual depende de una incrustación particular, el grafo dual de un grafo planar no es único, en el sentido de que el mismo grafo planar puede tener grafos duales no isomorfos . [11] En la imagen, los grafos azules son isomorfos pero sus grafos duales rojos no lo son. El dual rojo superior tiene un vértice con grado 6 (que corresponde a la cara exterior del grafo azul) mientras que en el grafo rojo inferior todos los grados son menores que 6.
Hassler Whitney demostró que si el grafo es 3-conexo entonces la incrustación, y por lo tanto el grafo dual, es único. [12] Por el teorema de Steinitz , estos grafos son exactamente los grafos poliédricos , los grafos de poliedros convexos. Un grafo planar es 3-conexo por vértices si y solo si su grafo dual es 3-conexo por vértices. Además, un grafo planar biconexo tiene una incrustación única, y por lo tanto también un dual único, si y solo si es una subdivisión de un grafo planar 3-conexo por vértices (un grafo formado a partir de un grafo planar 3-conexo por vértices reemplazando algunas de sus aristas por caminos). [13] Para algunos grafos planares que no son 3-conexos por vértices, como el grafo bipartito completo K 2,4 , la incrustación no es única, pero todas las incrustaciones son isomorfas. Cuando esto sucede, correspondientemente, todos los gráficos duales son isomorfos.
Dado que diferentes incrustaciones pueden dar lugar a diferentes grafos duales, comprobar si un grafo es dual de otro (sin conocer ya sus incrustaciones) es un problema algorítmico no trivial . En el caso de grafos biconexos, se puede resolver en tiempo polinomial utilizando los árboles SPQR de los grafos para construir una forma canónica para la relación de equivalencia de tener un dual mutuo compartido. Por ejemplo, los dos grafos rojos de la ilustración son equivalentes según esta relación. Sin embargo, en el caso de grafos planos que no están biconexos, esta relación no es una relación de equivalencia y el problema de comprobar la dualidad mutua es NP-completo . [14]
Un conjunto de corte en un grafo conexo arbitrario es un subconjunto de aristas definido a partir de una partición de los vértices en dos subconjuntos, incluyendo una arista en el subconjunto cuando tiene un punto final en cada lado de la partición. Eliminar las aristas de un conjunto de corte necesariamente divide el grafo en al menos dos componentes conexos. Un conjunto de corte mínimo (también llamado enlace) es un conjunto de corte con la propiedad de que cada subconjunto propio del conjunto de corte no es en sí mismo un corte. Un conjunto de corte mínimo de un grafo conexo necesariamente separa su grafo en exactamente dos componentes, y consiste en el conjunto de aristas que tienen un punto final en cada componente. [15] Un ciclo simple es un subgrafo conexo en el que cada vértice del ciclo es incidente a exactamente dos aristas del ciclo. [16]
En un grafo planar conexo G , cada ciclo simple de G corresponde a un conjunto de corte mínimo en el dual de G , y viceversa. [17] Esto puede verse como una forma del teorema de la curva de Jordan : cada ciclo simple separa las caras de G en las caras en el interior del ciclo y las caras del exterior del ciclo, y los duales de las aristas del ciclo son exactamente las aristas que cruzan desde el interior al exterior. [18] La circunferencia de cualquier grafo planar (el tamaño de su ciclo más pequeño) es igual a la conectividad de las aristas de su grafo dual (el tamaño de su conjunto de corte más pequeño). [19]
Esta dualidad se extiende desde los conjuntos de corte y ciclos individuales hasta los espacios vectoriales definidos a partir de ellos. El espacio de ciclos de un grafo se define como la familia de todos los subgrafos que tienen grado par en cada vértice; puede verse como un espacio vectorial sobre el cuerpo finito de dos elementos , con la diferencia simétrica de dos conjuntos de aristas actuando como la operación de adición vectorial en el espacio vectorial. De manera similar, el espacio de cortes de un grafo se define como la familia de todos los conjuntos de cortes, con la adición vectorial definida de la misma manera. Entonces, el espacio de ciclos de cualquier grafo planar y el espacio de cortes de su grafo dual son isomorfos como espacios vectoriales. [20] Por lo tanto, el rango de un grafo planar (la dimensión de su espacio de cortes) es igual al número ciclotómico de su dual (la dimensión de su espacio de ciclos) y viceversa. [11] Una base de ciclos de un grafo es un conjunto de ciclos simples que forman una base del espacio de ciclos (cada subgrafo de grado par puede formarse exactamente de una manera como una diferencia simétrica de algunos de estos ciclos). En el caso de los grafos planos ponderados por aristas (con pesos suficientemente generales como para que no haya dos ciclos con el mismo peso), la base de ciclo de peso mínimo del grafo es dual con respecto al árbol de Gomory-Hu del grafo dual, una colección de cortes anidados que juntos incluyen un corte mínimo que separa cada par de vértices del grafo. Cada ciclo de la base de ciclo de peso mínimo tiene un conjunto de aristas que son duales con respecto a las aristas de uno de los cortes del árbol de Gomory-Hu. Cuando los pesos de los ciclos pueden estar vinculados, la base de ciclo de peso mínimo puede no ser única, pero en este caso sigue siendo cierto que el árbol de Gomory-Hu del grafo dual corresponde a una de las bases de ciclo de peso mínimo del grafo. [20]
En los grafos planos dirigidos, los ciclos dirigidos simples son duales a los cortes dirigidos (particiones de los vértices en dos subconjuntos tales que todas las aristas van en una dirección, de un subconjunto al otro). Los grafos planos fuertemente orientados (grafos cuyo grafo subyacente no dirigido está conexo, y en los que cada arista pertenece a un ciclo) son duales a los grafos acíclicos dirigidos en los que ninguna arista pertenece a un ciclo. Para decirlo de otra manera, las orientaciones fuertes de un grafo plano conexo (asignaciones de direcciones a las aristas del grafo que resultan en un grafo fuertemente conexo ) son duales a las orientaciones acíclicas (asignaciones de direcciones que producen un grafo acíclico dirigido ). [21] De la misma manera, los dijoins (conjuntos de aristas que incluyen una arista de cada corte dirigido) son duales a los conjuntos de arcos de retroalimentación (conjuntos de aristas que incluyen una arista de cada ciclo). [22]
Un árbol de expansión puede definirse como un conjunto de aristas que, junto con todos los vértices del grafo, forma un subgrafo conexo y acíclico. Pero, por dualidad de corte-ciclo, si un conjunto S de aristas en un grafo plano G es acíclico (no tiene ciclos), entonces el conjunto de aristas duales a S no tiene cortes, de lo que se sigue que el conjunto complementario de aristas duales (las duales de las aristas que no están en S ) forma un subgrafo conexo. Simétricamente, si S es conexo, entonces las aristas duales al complemento de S forman un subgrafo acíclico. Por lo tanto, cuando S tiene ambas propiedades (es conexo y acíclico), lo mismo es cierto para el conjunto complementario en el grafo dual. Es decir, cada árbol de expansión de G es complementario a un árbol de expansión del grafo dual, y viceversa. Por lo tanto, las aristas de cualquier grafo planar y su dual pueden dividirse juntas (de múltiples maneras diferentes) en dos árboles de expansión, uno en el primal y otro en el dual, que juntos se extienden a todos los vértices y caras del grafo pero nunca se cruzan entre sí. En particular, el árbol de expansión mínimo de G es complementario al árbol de expansión máximo del grafo dual. [23] Sin embargo, esto no funciona para árboles de camino más corto , ni siquiera aproximadamente: existen grafos planares tales que, para cada par de un árbol de expansión en el grafo y un árbol de expansión complementario en el grafo dual, al menos uno de los dos árboles tiene distancias que son significativamente más largas que las distancias en su grafo. [24]
Un ejemplo de este tipo de descomposición en árboles entrelazados se puede ver en algunos tipos simples de laberintos , con una sola entrada y sin componentes desconectados de sus paredes. En este caso, tanto las paredes del laberinto como el espacio entre las paredes toman la forma de un árbol matemático. Si el espacio libre del laberinto se divide en celdas simples (como los cuadrados de una cuadrícula), entonces este sistema de celdas puede verse como una incrustación de un gráfico planar, en el que la estructura de árbol de las paredes forma un árbol de expansión del gráfico y la estructura de árbol del espacio libre forma un árbol de expansión del gráfico dual. [25] También se pueden ver pares similares de árboles entrelazados en el patrón en forma de árbol de arroyos y ríos dentro de una cuenca de drenaje y el patrón dual en forma de árbol de las líneas de cresta que separan los arroyos. [26]
Esta partición de las aristas y sus duales en dos árboles conduce a una prueba simple de la fórmula de Euler V − E + F = 2 para grafos planares con V vértices, E aristas y F caras. Cualquier árbol de expansión y su árbol de expansión dual complementario dividen las aristas en dos subconjuntos de V − 1 y F − 1 aristas respectivamente, y sumando los tamaños de los dos subconjuntos se obtiene la ecuación
que puede reorganizarse para formar la fórmula de Euler. Según Duncan Sommerville , esta prueba de la fórmula de Euler se debe a Geometrie der Lage de KGC Von Staudt (Nürnberg, 1847). [27]
En las incrustaciones de superficies no planas, el conjunto de aristas duales complementarias a un árbol de expansión no es un árbol de expansión dual. En cambio, este conjunto de aristas es la unión de un árbol de expansión dual con un pequeño conjunto de aristas adicionales cuyo número está determinado por el género de la superficie en la que está incrustado el gráfico. Las aristas adicionales, en combinación con las rutas en los árboles de expansión, se pueden utilizar para generar el grupo fundamental de la superficie. [28]
Cualquier fórmula de conteo que involucre vértices y caras que sea válida para todos los grafos planos puede transformarse por dualidad plana en una fórmula equivalente en la que se hayan intercambiado los roles de los vértices y las caras. La fórmula de Euler, que es autodual, es un ejemplo. Otra dada por Harary involucra el lema del apretón de manos , según el cual la suma de los grados de los vértices de cualquier grafo es igual al doble del número de aristas. En su forma dual, este lema establece que en un grafo plano, la suma de los números de lados de las caras del grafo es igual al doble del número de aristas. [29]
El grafo medial de un grafo plano es isomorfo al grafo medial de su dual. Dos grafos planos pueden tener grafos mediales isomorfos solo si son duales entre sí. [30]
Un gráfico plano con cuatro o más vértices es máximo (no se pueden agregar más aristas mientras se preserva la planaridad) si y solo si su gráfico dual es 3-conexo por vértices y 3-regular . [31]
Un grafo plano conexo es euleriano (tiene grado par en cada vértice) si y solo si su grafo dual es bipartito . [32] Un ciclo hamiltoniano en un grafo plano G corresponde a una partición de los vértices del grafo dual en dos subconjuntos (el interior y el exterior del ciclo) cuyos subgrafos inducidos son ambos árboles. En particular, la conjetura de Barnette sobre la hamiltonicidad de los grafos poliédricos bipartitos cúbicos es equivalente a la conjetura de que todo grafo plano maximal euleriano puede ser particionado en dos árboles inducidos. [33]
Si un grafo planar G tiene polinomio de Tutte T G ( x , y ) , entonces el polinomio de Tutte de su grafo dual se obtiene intercambiando x e y . Por esta razón, si algún valor particular del polinomio de Tutte proporciona información sobre ciertos tipos de estructuras en G , entonces intercambiar los argumentos del polinomio de Tutte dará la información correspondiente para las estructuras duales. Por ejemplo, el número de orientaciones fuertes es T G (0,2) y el número de orientaciones acíclicas es T G (2,0) . [34] Para grafos planares sin puentes , las coloraciones de grafos con k colores corresponden a flujos de cero en ninguna parte módulo k en el grafo dual. Por ejemplo, el teorema de los cuatro colores (la existencia de una coloración de 4 para cada grafo planar) se puede expresar de manera equivalente como afirmando que el dual de cada grafo planar sin puentes tiene un flujo de 4 en ninguna parte. El número de k -coloraciones se cuenta (hasta un factor fácilmente calculable) por el valor del polinomio de Tutte T G (1 − k ,0) y dualmente el número de k -flujos sin cero se cuenta por T G (0,1 − k ) . [35]
Un grafo st -planar es un grafo st-planar conectado con una orientación bipolar de ese grafo, una orientación que lo hace acíclico con una única fuente y un único sumidero, ambos requeridos para estar en la misma cara que el otro. Un grafo de este tipo puede convertirse en un grafo fuertemente conectado agregando una arista más, desde el sumidero hasta la fuente, a través de la cara externa. El dual de este grafo st-planar aumentado es en sí mismo la ampliación de otro grafo st -planar. [36]
En un grafo plano dirigido , el grafo dual puede hacerse dirigido también, orientando cada borde dual con un giro de 90° en el sentido de las agujas del reloj desde el borde primario correspondiente. [36] Estrictamente hablando, esta construcción no es una dualidad de grafos planos dirigidos, porque al partir de un grafo G y tomar el dual dos veces no se vuelve al propio G , sino que se construye un grafo isomorfo al grafo transpuesto de G , el grafo formado a partir de G invirtiendo todos sus bordes. Al tomar el dual cuatro veces se vuelve al grafo original.
El dual débil de un grafo plano es el subgrafo del grafo dual cuyos vértices corresponden a las caras acotadas del grafo primal. Un grafo plano es exteriormente plano si y solo si su dual débil es un bosque . Para cualquier grafo plano G , sea G + el multigrafo plano formado añadiendo un único vértice nuevo v en la cara no acotada de G , y conectando v a cada vértice de la cara exterior (varias veces, si un vértice aparece varias veces en el límite de la cara exterior); entonces, G es el dual débil del dual (plano) de G + . [37]
El concepto de dualidad se aplica tanto a grafos infinitos incrustados en el plano como a grafos finitos. Sin embargo, es necesario tener cuidado para evitar complicaciones topológicas como puntos del plano que no son parte de una región abierta disjunta del grafo ni parte de una arista o vértice del grafo. Cuando todas las caras son regiones acotadas rodeadas por un ciclo del grafo, una incrustación de grafos planos infinitos también puede verse como una teselación del plano, una cobertura del plano por discos cerrados (las teselas de la teselación) cuyos interiores (las caras de la incrustación) son discos abiertos disjuntos. La dualidad plana da lugar a la noción de una teselación dual , una teselación formada al colocar un vértice en el centro de cada teselación y conectar los centros de las teselas adyacentes. [38]
El concepto de teselación dual también se puede aplicar a particiones del plano en un número finito de regiones. En este caso, está estrechamente relacionado con la dualidad de grafos planos, pero no es exactamente igual. Por ejemplo, el diagrama de Voronoi de un conjunto finito de puntos es una partición del plano en polígonos dentro de los cuales un punto está más cerca que cualquier otro. Los puntos en la envoltura convexa de la entrada dan lugar a polígonos de Voronoi ilimitados, dos de cuyos lados son rayos infinitos en lugar de segmentos de línea finitos. El dual de este diagrama es la triangulación de Delaunay de la entrada, un grafo plano que conecta dos puntos por una arista siempre que exista un círculo que contenga esos dos puntos y ningún otro punto. Las aristas de la envoltura convexa de la entrada también son aristas de la triangulación de Delaunay, pero corresponden a rayos en lugar de segmentos de línea del diagrama de Voronoi. Esta dualidad entre diagramas de Voronoi y triangulaciones de Delaunay se puede convertir en una dualidad entre grafos finitos de dos maneras: añadiendo un vértice artificial en el infinito al diagrama de Voronoi, para que sirva como el otro punto final para todos sus rayos, [39] o tratando la parte acotada del diagrama de Voronoi como el dual débil de la triangulación de Delaunay. Aunque el diagrama de Voronoi y la triangulación de Delaunay son duales, su incrustación en el plano puede tener cruces adicionales más allá de los cruces de pares duales de aristas. Cada vértice del triángulo de Delaunay se posiciona dentro de su cara correspondiente del diagrama de Voronoi. Cada vértice del diagrama de Voronoi se posiciona en el circuncentro del triángulo correspondiente de la triangulación de Delaunay, pero este punto puede estar fuera de su triángulo.
El concepto de dualidad se puede extender a incrustaciones de grafos en variedades bidimensionales distintas del plano. La definición es la misma: hay un vértice dual para cada componente conexo del complemento del grafo en la variedad, y una arista dual para cada arista del grafo que conecta los dos vértices duales en cada lado de la arista. En la mayoría de las aplicaciones de este concepto, está restringido a incrustaciones con la propiedad de que cada cara es un disco topológico; esta restricción generaliza el requisito para grafos planares de que el grafo sea conexo. Con esta restricción, el dual de cualquier grafo incrustado en una superficie tiene una incrustación natural en la misma superficie, de modo que el dual del dual es isomorfo e isomorfamente incrustado en el grafo original. Por ejemplo, el grafo completo K 7 es un grafo toroidal : no es plano pero puede incrustarse en un toro, siendo cada cara de la incrustación un triángulo. Esta incrustación tiene al grafo de Heawood como su grafo dual. [40]
El mismo concepto funciona igualmente bien para superficies no orientables . Por ejemplo, K 6 puede incrustarse en el plano proyectivo con diez caras triangulares como el hemi-icosaedro , cuyo dual es el grafo de Petersen incrustado como el hemi-dodecaedro . [41]
Incluso los grafos planares pueden tener incrustaciones no planares, con duales derivados de esas incrustaciones que difieren de sus duales planares. Por ejemplo, los cuatro polígonos de Petrie de un cubo (hexágonos formados al eliminar dos vértices opuestos del cubo) forman las caras hexagonales de una incrustación del cubo en un toro . El grafo dual de esta incrustación tiene cuatro vértices que forman un grafo completo K 4 con aristas duplicadas. En la incrustación en toro de este grafo dual, las seis aristas incidentes a cada vértice, en orden cíclico alrededor de ese vértice, pasan dos veces por los otros tres vértices. A diferencia de la situación en el plano, esta incrustación del cubo y su dual no es única; el grafo cúbico tiene varias otras incrustaciones en toro, con diferentes duales. [40]
Muchas de las equivalencias entre las propiedades de los gráficos primarios y duales de los gráficos planares no pueden generalizarse a los duales no planares, o requieren un cuidado adicional en su generalización.
Otra operación sobre grafos incrustados en superficies es el dual de Petrie , que utiliza los polígonos de Petrie de la incrustación como caras de una nueva incrustación. A diferencia del grafo dual habitual, tiene los mismos vértices que el grafo original, pero generalmente se encuentra en una superficie diferente. [42] La dualidad de superficies y la dualidad de Petrie son dos de las seis operaciones de Wilson y juntas generan el grupo de estas operaciones. [43]
Un dual algebraico de un grafo conexo G es un grafo G * tal que G y G * tienen el mismo conjunto de aristas, cualquier ciclo de G es un corte de G * y cualquier corte de G es un ciclo de G * . Todo grafo plano tiene un dual algebraico, que en general no es único (cualquier dual definido por una incrustación en un plano servirá). Lo inverso es cierto, como lo establece Hassler Whitney en el criterio de planaridad de Whitney : [44]
El mismo hecho puede expresarse en la teoría de matroides . Si M es el matroide gráfico de un grafo G , entonces un grafo G * es un dual algebraico de G si y solo si el matroide gráfico de G * es el matroide dual de M. Entonces el criterio de planaridad de Whitney puede reformularse para afirmar que el matroide dual de un matroide gráfico M es en sí mismo un matroide gráfico si y solo si el grafo subyacente G de M es planar. Si G es planar, el matroide dual es el matroide gráfico del grafo dual de G. En particular, todos los grafos duales, para todas las diferentes incrustaciones planares de G , tienen matroides gráficos isomorfos. [45]
Para incrustaciones de superficies no planas, a diferencia de los duales planares, el grafo dual no es generalmente un dual algebraico del grafo primal. Y para un grafo no planar G , el matroide dual del matroide gráfico de G no es en sí mismo un matroide gráfico. Sin embargo, sigue siendo un matroide cuyos circuitos corresponden a los cortes en G , y en este sentido puede considerarse como un dual algebraico generalizado combinatoriamente de G . [46]
La dualidad entre grafos planos eulerianos y bipartitos se puede extender a los matroides binarios (que incluyen los matroides gráficos derivados de grafos planos): un matroide binario es euleriano si y solo si su matroide dual es bipartito . [32]
Los dos conceptos duales de circunferencia y conectividad de aristas se unifican en la teoría de matroides mediante la circunferencia de matroide : la circunferencia del matroide gráfico de un grafo planar es la misma que la circunferencia del grafo, y la circunferencia del matroide dual (el matroide gráfico del grafo dual) es la conectividad de aristas del grafo. [19]
Además de su uso en la teoría de grafos, la dualidad de grafos planos tiene aplicaciones en varias otras áreas de estudio matemático y computacional.
En los sistemas de información geográfica , las redes de flujo (como las redes que muestran cómo fluye el agua en un sistema de arroyos y ríos) son duales con respecto a las redes celulares que describen las divisorias de aguas . Esta dualidad se puede explicar modelando la red de flujo como un árbol de expansión en un gráfico de cuadrícula de una escala apropiada, y modelando la divisoria de aguas como el árbol de expansión complementario de las crestas en el gráfico de cuadrícula dual. [47]
En la visión artificial , las imágenes digitales se dividen en pequeños píxeles cuadrados , cada uno de los cuales tiene su propio color. El gráfico dual de esta subdivisión en cuadrados tiene un vértice por píxel y un borde entre pares de píxeles que comparten un borde; es útil para aplicaciones que incluyen la agrupación de píxeles en regiones conectadas de colores similares. [48]
En geometría computacional , la dualidad entre los diagramas de Voronoi y las triangulaciones de Delaunay implica que cualquier algoritmo para construir un diagrama de Voronoi puede convertirse inmediatamente en un algoritmo para la triangulación de Delaunay, y viceversa. [49] La misma dualidad también puede usarse en la generación de mallas de elementos finitos . El algoritmo de Lloyd , un método basado en diagramas de Voronoi para mover un conjunto de puntos en una superficie a posiciones espaciadas más uniformemente, se usa comúnmente como una forma de suavizar una malla de elementos finitos descrita por la triangulación dual de Delaunay. Este método mejora la malla al hacer que sus triángulos tengan un tamaño y una forma más uniformes. [50]
En la síntesis de circuitos CMOS , la función a sintetizar se representa como una fórmula en álgebra de Boole . Luego, esta fórmula se traduce en dos multigrafos serie-paralelo . Estos grafos se pueden interpretar como diagramas de circuitos en los que los bordes de los grafos representan transistores , controlados por las entradas de la función. Un circuito calcula la función en sí misma y el otro calcula su complemento. Uno de los dos circuitos se deriva convirtiendo las conjunciones y disyunciones de la fórmula en composiciones de grafos en serie y en paralelo, respectivamente. El otro circuito invierte esta construcción, convirtiendo las conjunciones y disyunciones de la fórmula en composiciones de grafos en serie y en paralelo. [51] Estos dos circuitos, aumentados por un borde adicional que conecta la entrada de cada circuito con su salida, son grafos duales planares. [52]
La dualidad de los poliedros convexos fue reconocida por Johannes Kepler en su libro de 1619 Harmonices Mundi . [53] Los grafos duales planares reconocibles, fuera del contexto de los poliedros, aparecieron ya en 1725, en la obra publicada póstumamente por Pierre Varignon , Nouvelle Méchanique ou Statique . Esto fue incluso antes del trabajo de 1736 de Leonhard Euler sobre los Siete Puentes de Königsberg que a menudo se considera el primer trabajo sobre teoría de grafos . Varignon analizó las fuerzas sobre sistemas estáticos de puntales dibujando un grafo dual de los puntales, con longitudes de aristas proporcionales a las fuerzas sobre los puntales; este grafo dual es un tipo de diagrama de Cremona . [54] En relación con el teorema de los cuatro colores , los gráficos duales de los mapas (subdivisiones del plano en regiones) fueron mencionados por Alfred Kempe en 1879, y extendidos a los mapas en superficies no planas por Lothar Heffter en 1891. [55] La dualidad como una operación en gráficos planos abstractos fue introducida por Hassler Whitney en 1931. [56]
tenga en cuenta que "puente" y "bucle" son conceptos duales.
¿Es esta la ilustración más antigua de dualidad entre gráficos planares?.