grafos:incorp [WikiMat]

Essa página está em modo somente de leitura. Você pode visualizar a fonte, mas não alterá-la. Informe-se com o administrador do Wiki, caso você ache que isso está incorreto.
==== Incorporações planares e Teorema de Whitney ====

Uma **imersão (incorporação)** no plano, ou **imersão planar**, de um grafo (abstrato) $G$ é um $\pi ^{-1}(x)$-isomorfismo entre $G$ e um grafo plano $H$. Este último será chamado de **desenho** de $G$. Nem sempre distinguiremos notacionalmente entre os vértices e arestas de $G$ e de $H$. Investigaremos como duas imersões planares de um grafo podem diferir.

Como devemos medir a semelhança de duas incorporações $\rho : G \to H$ e $\rho ': G \to H'$ de um grafo planar $G$? Uma maneira óbvia de fazer isso é considerar o isomorfismo canônico $\sigma := \rho ' \circ \rho ^{-1}$ entre $H$ e $H'$ como grafos abstratos e perguntar quanto de sua posição no plano esse isomorfismo respeita ou preserva. Por exemplo, se $\sigma$ é induzido por uma simples rotação do plano, dificilmente deveríamos considerar $\rho$ e $\rho '$ como maneiras genuinamente diferentes de desenhar $G$.

Portanto, vamos começar considerando qualquer isomorfismo abstrato $\sigma :V \to V'$ entre dois grafos planos $H =(V,E)$ e $H' =(V',E')$, com conjuntos de faces $F(H) =: F$ e $F(H')=F'$, digamos, e tentar medir até que ponto $\sigma$ respeita ou preserva as características de $H$ e $H'$ como grafos planos. A seguir, vamos propor três critérios para isso em ordem decrescente de rigor (e ordem crescente de facilidade de manuseio) e, então, provar que, para a maioria dos gráficos, esses três critérios acabam concordando. Em particular, aplicado ao ismorfismo $\sigma = \rho ' \circ \rho ^{-1}$  considerado anteriormente, todos os três critérios dirão que há essencialmente apenas uma maneira de desenhar um grafo $3$-conexo.

Nosso primeiro critério para medir quão bem nosso isomorfismo abstrato $\sigma$ preserva as características planas de $H$ e $H'$ é talvez o mais natural. Intuitivamente, gostaríamos de chamar $\sigma$ de 'topológico' se for induzido por um homeomorfismo do plano $\mathbb{R}^2$ para si mesmo. Para evitar ter que conceder às faces externas de $H$ e $H'$ um status especial, no entanto, fazemos um desvio pelo homeomorfismo $\pi : S^2 \setminus \{(0,0,1)\} \to \mathbb{R}^2$ escolhido na [[.pretopology|aqui]]: chamamos $\sigma$ de **isomorfismo topológico** entre os grafos planos $H$ e $H'$ se existe um homeomorfismo $\varphi : S^2 \to S^2$ tal que $\psi := \pi \circ \varphi \circ \pi ^{-1}$ induz $\sigma$ em $V \cup E$. Mais formalmente: pedimos que $\psi$ concorde com $\sigma$ em $V$, e que mapeie cada aresta plana $xy \in H$ na aresta plana $\sigma (x) \sigma (y) \in H'$. A menos que $\psi$ fixe o ponto $(0,0,1)$, o mapa $\psi$ será indefinido em $\pi (\varphi ^{-1} (0,0,1))$.

Na figura abaixo, por exemplo, temos dois desenhos de um grafo que não são topologicamente isomórficos:

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

Pode-se mostrar que, até o isomorfismo topológico, as faces internas e externas de fato não são mais diferentes: se escolhermos como $\varphi$ uma rotação de $S^2$ mapeando a imagem $\pi ^{-1}$ de um ponto de alguma face interna de $H$ para o pólo norte de $(0,0,1)$ de $S^2$, então $\psi$ mapeia o restante dessa face para a face externa de $\psi (H)$. Para garantir que as arestas de $\psi (H)$ sejam novamente lineares por partes, pode-se ter que ajustar $\psi$ um pouco.

Se $\sigma$ é um isomorfismo topológico como acima, então , exceto possivelmente por um par de pontos ausentes onde $\psi$ ou $\psi ^{-1}$ é indefinido, $\psi$ mapeia as faces de $H$ nas de $H'$. Dessa forma, $\sigma$ se estende naturalmente a uma bijeção $\sigma : V \cup E \cup F \to V' \cup E' \cup F'$ que preserva incidência de vértices, arestas e faces.

Vamos destacar esta última propriedade de um isomorfismo topológico como o segundo critério para quão bem um isomorfismo abstrato entre grafos planos respeita sua posição no plano: vamos chamar $\sigma$ de **isomorfismo combinatório** dos grafos planos $H$ e $H'$ se puder ser estendido a uma bijeção  $\sigma : V \cup E \cup F \to V' \cup E' \cup F'$  que preserva a incidência não apenas de vértices com arestas, mas também de vértices e arestas com faces.Formalmente: exigimos que um vértice ou aresta $x \in H$ esteja no limite de uma face $f \in F$ se, e somente se, $\sigma (x)$ estiver no limite da face $\sigma (f)$.

Na figura abaixo, por exemplo, temos dois desenhos de grafos que são combinatorialmente isomórficos, mas não topologicamente:

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

Se $\sigma$ é um isomorfismo combinatório dos grafos planos $H$ e $H'$, ele mapeia os limites das faces de $H$ aos de $H'$. Vamos escolher essa propriedade como nosso terceiro critério e chamar $\sigma$ de **isomorfismo grafo-teórico** dos grafos planos $H$ e $H'$ se

$$\{\sigma (H[f]): f \in F\} = \{H'[f']: f' \in F'\}.$$

Assim, não mais acompanhamos qual face é limitada por um determinado subgrafo: a única informação que mantemos é se um subgrafo limita alguma face ou não, e exigimos que $\sigma$ mapeie os subgrafos que fazem uns com os outros. À primeira vista, este terceiro critério pode parecer um pouco menos natural do que os dois anteriores. No entanto, tem a vantagem prática de ser formalmente mais fraco e, portanto, mais fácil de verificar e, além disso, será equivalente aos outros dois na maioria dos casos.

Como vimos , todo isomorfismo topológico entre dois grafos planos também é combinatório, e todo isomorfismo combinatório também é grafo-teórico. O teorema a seguir mostra que, para a maioria dos grafos, o inverso também é verdadeiro:

<WRAP round box 100%>
=== Teorema 1 ===
$(i)$ //Todo isomorfismo grafo-teórico entre dois grafos planos é combinatório. Sua extensão para uma bijeção de face é única se, e somente se, o grafo não for um ciclo.//

$(ii)$ //Todo isomorfismo combinatório entre dois grafos planos $2$-conexos é topológico.//
</WRAP>

<WRAP round box 100%>
//**Demonstração:**//
Sejam $H = (V,E)$ e $H' = (V',E')$ dois grafos planos, coloque $F(H) =: F$ e $F(H') = F'$, e seja $\sigma :V \to V'$ um isomorfismo entre os grafos abstratos subjacentes. Estenda $\sigma$ para um mapa $V \cup E \to V' \cup E'$ deixando $\sigma (xy) := \sigma (x) \sigma (y)$.

$(i)$ Se $H$ é um ciclo, a afirmação decorre do [[grafos:pretopology#teorema_da_curva_de_jordan_para_poligonos | teorema da curva de Jordan]]. Assumimos agora que $H$ não é um ciclo. Sejam $\mathcal{B}$ e $\mathcal{B}'$ os conjuntos de todos os limites de face em $H$ e $H'$, respectivamente. Se $\sigma$ é um isomorfismo grafo-teórico, então o mapa $B \to \sigma (B)$ é uma bijeção entre $\mathcal{B}$ e $\mathcal{B}'$. Pelo [[grafos:topicosplan#lema |Lema]], a aplicação $f \to H[f]$ é uma bijeção entre $F$ e $\mathcal{B}$, e da mesma forma para $F'$ e $\mathcal{B}'$. A composição dessas três bijeções é uma bijeção entre $F$ e $F'$, que escolhemos como $\sigma F \to F'$. Por construção, essa extensão de $\sigma$ para $V \cup E \cup F$ preserva as incidências (e é único com essa propriedade), então $\sigma$ é de fato um isomorfismo combinatório.

$(ii)$ Vamos assumir que $H$ é $2$-conexo, e que $\sigma$ é um isomorfismo combinatório. Temos que construir um homeomorfismo $\varphi : S^2 \to S^2$ que, para cada vértice ou aresta plana $x \in H$, mapeia $\pi ^{-1}(x)$ para $\pi ^{-1}(\sigma (x))$. Como $\sigma$ é um isomorfismo combinatório, $\tilde{\sigma} : \pi^{-1} \circ \sigma \circ \pi$ é uma bijeção que preserva a incidência dos vértices, arestas e faces de $\tilde{H} := \pi^{-1}(H)$ aos vértices, arestas e rostos de $\tilde{H}' := \pi^{-1}(H')$. (Por 'vértices, arestas e faces' de $\tilde{H}$ e $\tilde{H'}$ queremos dizer as imagens sob $\pi^{-1}$ dos vértices, arestas e faces de $H$ e $H'$ (mais $(0,0,1)$ no caso da face externa). Seus conjuntos serão denotados por $V(\tilde{H}),E(\tilde{H}),F(\tilde{H})$ e $V(\tilde{H'}),E(\tilde{H'}),F(\tilde{H'})$ e a incidência é definida como herdada de $H$ e $H'$.)

Definindo $\tilde{\sigma}$ a partir de $\sigma$:

{{ :grafos:graphs106.png?300 |}}

Construímos $\varphi$ em três passos. Vamos primeiro definir $\varphi$ no conjunto de vértices de $\tilde{H}$, definindo $\varphi (x):= \tilde{\varphi}(x)$ para todo $x \in V(\tilde{H})$. Isso é trivialmente um homeomorfismo entre $V(\tilde{H})$ e $V(\tilde{H'})$.

Como segundo passo, agora estendemos $\varphi$ a um homeomorfismo entre $\tilde{H}$ e $\tilde{H'}$ induz $\tilde{\sigma}$ em $V(\tilde{H}) \cup E(\tilde{H})$. Podemos fazer isso aresta por aresta, como segue. Toda aresta $xy$ de $\tilde{H}$ é homeomorfa à aresta $\tilde{\sigma}(xy) = \varphi (x) \varphi(y)$ de $\tilde{H'}$, por um homeomorfismo mapeando $x$ para $\varphi (x)$ e $y$ para $\varphi (y)$. Então a união de todos esses homeomorfismos , um para cada aresta de $\tilde{H}$, é de fato um homeomorfismo entre $\tilde{H}$ e $\tilde{H'}$, nossa extensão desejada de $\varphi$ para $\tilde{H}$: tudo o que temos que verificar é a continuidade nos vértices (onde os homeomorfismos de arestas se sobrepõem), e isso segue imediatamente de nossa suposição de que os dois grafos e suas arestas individuais carregam a topologia do subespaço em $\mathbb{R}^3$.

No terceiro passo agora estendemos nosso homeomorfismo $\varphi : \tilde{H} \to \tilde{H'}$ para todo $S^2$. Isso pode ser feito de forma análoga ao segundo passo, face a face. Pela [[grafos:topicosplan#proposicao_2 | Proposição 2]], todos os limites de face em $\tilde{H}$ e $\tilde{H'}$ são ciclos. Agora, se $f$ é uma face de $\tilde{H}$ e $C$ é seu limite, então $\tilde{\sigma}(C) := \bigcup \{\tilde{\sigma}(e) | e \in E(C)\}$ limita a face $\tilde{\sigma}(f)$ de $\tilde{H'}$. Pelo [[grafos:pretopology#teorema |Teorema]], podemos estender o homeomorfismo $\varphi : C \to \tilde{\sigma}(f)$ definido até agora para um homeomorfismo de $C \cup f$ para $\tilde{\sigma}(C) \cup \tilde{\sigma}(f)$. Finalmente, tomamos a união de todos esses homeomorfismos, um para cada face $f$ de $\tilde{H}$, como nosso homeomorfismo desejado $\varphi : S^2 \to S^2$, como antes, continuidade é facilmente verificado.


<wrap right>$\square$</wrap>
</WRAP>

Voltemos agora ao nosso objetivo original, a definição de equivalência para incorporação planar. Vamos chamar duas incorporações planares $\rho,\rho '$ de um grafo $G$ topologicamente (respectivamente, combinatorialmente) equivalentes se $\rho ' \circ \rho^{-1}$ é um isomorfismo topológico (respectivamente, combinatório) entre $\rho (G)$ e $\rho '(G)$. Se $G$ é $2$-conexo, as duas definições coincidem pelo Teorema $1$ acima, e simplesmente falamos de **incorporações equivalentes**. Claramente, esta é de fato uma relação de equivalência no conjunto de iincorporações planares de qualquer grafo dado.

Observe que dois desenhos de $G$ resultantes de incorporações inequivalentes podem muito bem ser topologicamente isomórficos: para a equivalência de duas incorporações, pedimos não apenas que algum isomorfismo (topológico ou combinatório) exista entre as imagens, mas que o isomorfismo canônico $\rho ' \circ \rho^{-1}$ seja um isomorfismo topológico ou combinatória.

Mesmo no sentido forte, grafos $3$-conexos têm apenas uma incorporação até a equivalência:

<WRAP round box 100%>
=== Teorema de Whitney (1933) ===
//Quaisquer duas incorporações planares de um grafo $3$-conexo são equivalentes.//
</WRAP>


<WRAP round box 100%>
//**Demonstração:**//
Seja $G$ um grafo $3$-conexo com incorporações planares $\rho : G \to H$ e $\rho ': G \to H'$, pelo Teorema $1$ acima é suficiente mostrar que $\rho ' \circ \rho^{-1}$ é um isomorfismo grafo-teorico, ou seja, que $\rho (C)$ limita uma face de $H$ se, e somente se, $\rho '(C)$ limita uma face de $H'$, para todo subgrafo $C \subseteq G$. Mas isso segue imediatamente da [[grafos:limgrafoscub#proposicao_1 |Proposição 1]].

<wrap right>$\square$</wrap>
</WRAP>

----

<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. 98-102. Acesso em 12/04/2023.

</WRAP>