grafos:planeduality [WikiMat]

==== Dualidade Plana ====

Usaremos o [[grafos:criterionplanarity#teorema_maclane| Teorema de MacLane]] para descobrir outra conexão entre planaridade e estrutura algébrica: uma conexão entre a dualidade dos grafos planos e a dualidade do ciclo e espaço de corte.

<WRAP round box 100%>
=== Definição===
//Um **multigrafo plano** é um par $G=(V,E)$ de conjuntos finitos (de vértices e arestas, respectivamente) satisfazendo as seguintes condições://

$(i) V \subseteq \mathbb{R}^2;$

$(ii)$ //cada aresta é um arco entre dois vértices ou um polígono contendo exatamente um vértice (seu ponto final);//

$(iii)$ //além de seu(s) próprio(s) ponto(s) final(is), uma aresta não contém nenhum vértice e nenhum ponto de qualquer outra aresta.//

</WRAP>

Usaremos termos definidos para grafos planos livremente para multigrafos planos. Observe que, como nos multigrafos abstratos, tanto os loops quanto as arestas duplas contam como ciclos.

Consideremos o multigrafo plano $G$:

{{ :grafos:graph152.png?400 |}}

Coloquemos um novo vértice dentro de cada face de $G$ e liguemos esses novos vértices para formar outro multigrafo plano $G^*$, como segue: para cada aresta $e$ de $G$ ligamos os dois novos vértices nas faces incidentes com $e$ por uma aresta $e^*$ que se cruza $e$; se $e$ é incidente com apenas uma face, nós anexamos um laço $e^*$ ao novo vértice naquela face, cruzando novamente a aresta $e$. O multigrafo plano $G^*$ formado desta forma é então dual a $G$ no seguinte sentido: se aplicarmos o mesmo procedimento acima para $G^*$, obtemos um multigrafo plano muito similar a $G$; de fato, o próprio $G$ pode ser reobtido de $G^*$ dessa maneira.

Para tornar essa ideia mais precisa, sejam $G=(V,E)$ e $(V^*,E^*)$ quaisquer dois multigrafos planos e coloque $F(G) =: F$ e $F((V^*,E^*))=: F^*$. Chamamos $(V^*,E^*)$ de plano dual de $G$ e escrevemos $(V^*,E^*) =: G^*$, se houver bijeções

$$F \to V^* \qquad E \to E^* \qquad V \to F^*$$

$$ f \mapsto v^*(f) \qquad e \mapsto e^* \qquad v \mapsto f^*(v)$$

que satisfaçam as seguintes condições:

$(i) v^{*}(f) \in f, \forall f \in F;$

$(ii) |e^{*} \cap G|=|\dot e^{*} \cap \dot e| = |e \cap G^{*}|=1, \forall e \in E$, e em cada um $e$ e $e^*$ este ponto é um ponto interno de um segmento de linha reta;

$(iii) v \in f^{*}(v), \forall v \in V.$

----

Todo multigrafo plano conexo tem um plano dual. De fato, para satisfazer a condição $(i)$, começamos escolhendo de cada face $f$ de $G$ um ponto $v^*(f)$ como um vértice para $G^*$. Podemos então ligar esses vértices por arcos independentes conforme exigido por $(ii)$, e usar a conectividade de $G$ mostrar que existe de fato uma bijeção $V \to F^*$ satisfazendo $(iii)$.

Se $G^*_1$ e $G^*_2$ são dois planos duais de $G$, então claramente $G^*_1 \simeq G^*_2$; de fato, pode-se mostrar que a bijeção natural $v^*_1(f) \mapsto v^*_2(f)$ é um isomorfismo topológico entre $G^*$ e $G$. Nesse sentido, podemos falar do plano dual $G^*$ de $G$.

Finalmente, $G$ é um plano dual de $G^*$. De fato, isso é testemunhado pelos mapas inversos das bijeções da definição de $G^*$: definindo $v^*(f^*(v)) := v$ e $f^*(v^*(f)) := f$ para $f^*(v) \in F^*$ e $v^*(f) \in V^*$, vemos que as condições $(i)$ e $(iii)$ para $G^*$ se transforma em $(iii)$ e $(i)$ para $G$, enquanto a condição $(ii)$ é simétrica em $G$ e $G^*$. Como os duais são facilmente vistos como conecos, essa simetria implica que a conectividade também é uma condição necessária para que $G$ tenha um dual .

Talvez o aspecto mais interessante da dualidade planar seja que ela relaciona geometricamente dois tipos de conjuntos de arestas, ciclos e limites, que vimos anteriormente serem relacionados algebricamente ([[grafos:algebralinbas#teorema_1|Teorema]]):

<WRAP round box 100%>
=== Proposição 1 ===
//Para qualquer multigrafo plano conexo $G$, um conjunto de arestas $E \subseteq E(G)$ é o conjunto de arestas de um ciclo em $G$ se,e somente se, $E^* := \{e^* \mid e \in E\}$ é uma ligação em $G^*$.//
</WRAP>

<WRAP round box 100%>
//**Demonstração:**//

Pelas condições $(i)$ e $(ii)$ na definição de $G^*$, dois vértices $v^*(f_1)$ e $v^*(f_2)$ de $G^*$ estão na mesma componente de $G^*-E^*$ se, e somente se, $f_1$ e $f_2$ estão na mesma região de $\mathbb{R}^2 \setminus \bigcup E$: todo caminho $v^*(f_1)-v^*(f_2)$ em $G^*-E^*$ é um arco entre $f_1$ e $f_2$ em $\mathbb{R}^2 \setminus \bigcup E$ e, reciprocamente, cada um desses arcos $P$ (com $P \cap V(G) = \emptyset$) define um passeio em $G^*-E^*$ entre $v^*(f_1)$ e $v^*(f_2)$.

Agora, se $C \subseteq G$ é um ciclo e $E=E(C)$ então, pelo [[grafos:pretopology#teorema_da_curva_de_jordan_para_poligonos|Teorema da curva de Jordan]] e pela correspondência acima, $G^*-E^*$ tem exatamente duas componentes. Então $E^*$ é uma ligação de $G^*$, um corte mínimo não vazio.

Reciprocamente, se $E \subseteq E(G)$ é tal que $E^*$ é um corte em $G^*$ então, pela [[grafos:topicosplan#proposicao_1|Proposição]] e a correspondência acima , $E$ contém as arestas de um ciclo $C \subseteq G$. Se $E^*$ é uma ligação, $E$ não pode conter nenhuma outra aresta (pela implicação mostrada antes). Daí $E=E(C)$.

</WRAP>
----

A proposição acima sugere a seguinte generalização da dualidade plana para multigrafos abstratos. Chame um multigrafo $G^*$ de um //dual abstrato// de um multigrafo $G$ se $E(G^*)=E(G)$ e as ligações em $G^*$ são precisamente os conjuntos de arestas de ciclos em $G$. (Nem $G$ nem $G^*$ precisam ser conexos agora).

A correspondência entre ciclos e vínculos se estende aos espaços que eles geram:

<WRAP round box 100%>
=== Proposição 2 ===
//Se $G^*$ é um dual abstrato de $G$, então o espaço de corte de $G^*$ é o espaço de ciclo de $G$, ou seja,//

$$\mathcal{B}(G^*) = \mathcal{C}(G).$$
</WRAP>

<WRAP round box 100%>
//**Demonstração:**//

Como os ciclos de $G$ são precisamente as ligações de $G^*$, o subespaço $\mathcal{C}(G)$ que eles geram em $\varepsilon (G) = \varepsilon (G^*)$ é o mesmo que o subespaço gerado pelas ligações em $G^*$. Pelo [[grafos:algebralinbas#lema|Lema]], este é o espaço $\mathcal{B}(G^*)$.

</WRAP>

Pelo [[grafos:algebralinbas#teorema_1|Teorema]], a Proposição $2$ logo acima implica imediatamente que se $G^*$ é um dual abstrato de $G$, então $G$ é um dual abstrato de $G^*$. Pode-se mostrar que se $G$ é $3$-conexo, então $G^*$ é único (até o isomorfismo e a adição de vértices isolados). Pelo [[grafos:2conexo#lema_2|Lema]], um subconjunto não vazio de $E(G)=E(G^*)$ é o conjunto de arestas de um bloco de $G$ se, e somente se, ele é o conjunto de arestas de um bloco de $G^*$. Pelo [[grafos:2conexo#lema_1|Lema]], isso implica que os blocos de $G^*$ são duais dos blocos de $G$.

----

Embora a noção de dualidade abstrata tenha surgido como uma generalização da dualidade plana, poderia ter sido diferente. Já sabíamos do [[grafos:algebralinbas#teorema_1|Teorema]] que os ciclos e as ligações de um grafo formam conjuntos naturais e relacionados de arestas. Não seria impensável perguntar se, para alguns grafos, a ortogonalidade entre essas coleções de conjuntos de arestas poderia dar a eles padrões de interseção suficientemente semelhantes para que uma coleção formando os ciclos em um grafo pudesse formar as ligações em outro, e vice-versa. Em outras palavras, para quais grafos podemos mover todo o seu conjunto de arestas para um novo conjunto de vértices, redefinindo incidências, de forma que precisamente aqueles conjuntos de arestas que antes formavam ciclos agora se tornam ligações (e vice-versa)? Coloque desta forma, parece surpreendente que isso possa ser alcançado, muito menos para uma classe tão grande e natural de grafos como todos os grafos planares.

Como um dos destaques da teoria da planaridade clássica, mostramos agora que os grafos planares são precisamente aqueles para os quais isso pode ser feito. //Admitir um dual abstrato aparece assim como um novo critério de planaridade.// Por outro lado, o teorema pode ser lido como uma surpreendente caracterização topológica da propriedade igualmente fundamental de admitir um dual abstrato:

<WRAP round box 100%>
=== Teorema (Whitney) ===
//Um grafo é planar se, e somente se, tiver um dual abstrato.//
</WRAP>

<WRAP round box 100%>
//**Demonstração:**//

Seja $G$ um grafo planar e considere qualquer desenho. Cada componente $C$ deste desenho tem um plano dual $C^*$. Considere estes $C^*$ como multigrafos abstratos, e seja $G^*$ sua união disjunta. Então as ligações de $G^*$ são precisamente as de $C^*$, o que pela Proposição $2$,logo acima, correspondem aos ciclos em $G$.

Inversamente, suponha que $G$ tenha um dual abstrato $G^*$. Para provar que $G$ é planar, basta pelo [[grafos:criterionplanarity#teorema_maclane|Teorema de MacLane]] e pela Proposição $2$, logo acima, mostrar que $\mathcal{B}(G^*)$ tem uma base esparsa. Pela [[grafos:algebralinbas#proposicao_2| proposição]], possui.

</WRAP>

A teoria da dualidade para grafos abstratos e planos pode ser estendida para grafos infinitos. Como estes podem ter vínculos infinitos, seus duais devem então ter 'ciclos infinitos'.

----

<WRAP round info>
=== Referências ===
  * Reinhard Diestel. [[https://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch4.pdf |“Graph Theory”]] .5th Electronic Edition 2016, pp. 110-113. Acesso em 07/06/2023.

</WRAP>