Diferenças

Aqui você vê as diferenças entre duas revisões dessa página.

--- grafos:planeduality [2023/06/06 16:39] – edição externa 127.0.0.1
+++ grafos:planeduality [2023/06/07 14:04] (atual) – edição externa 127.0.0.1
@@ Linha 48: / Linha 48: @@
 <WRAP round box 100%>
-=== Proposição ===
+=== 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>
-Dem.:
-pelas condições (i) e (ii) na definição de G, dois vértices V e V de G estão na mesma componente de G se e somente se F e F estão na mesma região de R: todo caminho V em G é um arco entre F e F em R e, reciprocamente, cada um desses arcos P define um passeio em G entre V e V.
+<WRAP round box 100%>
+//**Demonstração:**//
-Agora, se C é um ciclo e E então, pelo teorema da curva de Jordan e pela correspondência acima, G tem exatamente dois componentes. Então E é uma ligação de G, um corte mínimo não vazio.
+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)$.
-Reciprocamente, se E é tal que E é um corte em G então, pela Proposição 4.2.4 e a correspondência acima , E contém as arestas de um ciclo C. Se E é uma ligação, E não pode conter nenhuma outra aresta (pela implicação mostrado antes). Daí E=E.
+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 4.6.1 sugere a seguinte generalização da dualidade plana para multigrafos abstratos. (A seguir, usaremos alguns lemas de capítulos anteriores que foram declarados apenas para gráficos. Esses lemas se estendem a multigrafos com provas inalteradas.) chame um multigrafo G de um dual abstrato de um multigrafo G se E e as ligações em G são precisamente os conjuntos de arestas de ciclos em G. (nem G nem G precisam ser conectados agora).
+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:
-Teorema 4.6.2
+<WRAP round box 100%>
-Se G é um dual abstrato de D, então o espaço de corte de G é o espaço de ciclo de G, ou seja,
+=== 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,//
-Dem.:
+$$\mathcal{B}(G^*) = \mathcal{C}(G).$$
+</WRAP>
-Como os ciclos de G são precisamente as ligações de G, o subespaço C que eles geram em K é o mesmo que o subespaço gerado pelas ligações em G. Pelo lema 1.9.3, este é o espaço B.
+<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^*)$.
-Pelo teorema 1.9.4, a proposição 4.6.2 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 Lema 3.1.3, um subconjunto não vazio de E é o conjunto de arestas de um bloco de G se e somente se ele é o conjunto de arestas de um bloco de G. pelo Lema 3.1.2, isso implica que os blocos de G são duais dos blocos de G.
+</WRAP>
-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.
+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$.
-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
+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.
-Um grafo é planar se e somente se tiver um dual abstrato.
-dem.:
+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:
-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.
-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.
+<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'.
 ----
-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>