| Ambos lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior |
| grafos:planeduality [2023/06/07 13:45] – piva | grafos:planeduality [2023/06/07 14:04] (atual) – edição externa 127.0.0.1 |
|---|
| ---- | ---- |
| |
| Embora a noção de dualidade abstrata tenha surgido como uma generalização da dualidade plana, poderia ter sido diferente. Já sabíamos do Teorema 1.9.4 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 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)? Pu 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. | 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. | 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: |
| |
| Teorem 4.6.3 | <WRAP round box 100%> |
| Um grafo é planar se e somente se tiver um dual abstrato. | === Teorema (Whitney) === |
| | //Um grafo é planar se, e somente se, tiver um dual abstrato.// |
| | </WRAP> |
| |
| dem.: | <WRAP round box 100%> |
| 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, que pela Proposição 4.6.2 correspondem aos ciclos em G. | //**Demonstração:**// |
| |
| Inversamente, suponha que G tenha um dual abstrato G. Para provar que G é planar, basta pelo teorema 4.5.1 e pela proposição 4.6.2 mostrar que B tem uma base esparsa. Pela proposição 1.9.2, sim. | 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'. |
| |
| ---- | ---- |
| |
| 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'. Tais coisas existem sim, e são fascinantes: surgem como círculos topológicos em um espaço formado pelo grafo e suas extremidades; consulte o Capítulo 8.6 | <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> |