| Próxima revisão | Revisão anterior |
| grafos:incorp [2023/04/13 15:06] – criada piva | grafos:incorp [2023/08/02 14:13] (atual) – edição externa 127.0.0.1 |
|---|
| ==== Incorporações planares e Teorema de Whitney ==== | ==== Incorporações planares e Teorema de Whitney ==== |
| |
| Uma **imersão (incorporação)** no plano, ou **imersão planar**, de um grafo (abstrato) $G$ é um iso$\pi ^{-1}(x)$morfismo 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. | 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$. | 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$. |
| |
| 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. | 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> | </WRAP> |
| |
| |
| <WRAP round box 100%> | <WRAP round box 100%> |
| //**demonstração:**// | //**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]]. | 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> | </WRAP> |