grafos:graphplanar

Diferenças

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

Link para esta página de comparações

Ambos lados da revisão anterior Revisão anterior
Próxima revisão		 Revisão anterior
grafos:graphplanar [2023/04/20 10:00] – pivagrafos:graphplanar [2023/04/20 14:09] (atual) – edição externa 127.0.0.1
Linha 16: Linha 16:
 //**Demonstração:**// //**Demonstração:**//
 O resultado segue da aplicação da [[grafos:limgrafoscub#proposicao_2 |Proposição 2]] e do [[grafos:eulersform#corolario_1 |Corolário 1]]. O resultado segue da aplicação da [[grafos:limgrafoscub#proposicao_2 |Proposição 2]] e do [[grafos:eulersform#corolario_1 |Corolário 1]].
 +
 +<wrap right>$\square$</wrap>
 </WRAP> </WRAP>
  
Linha 40: Linha 42:
 Se cada uma das cinco árvores $T_{x}$ é um $TK_{1,4}$, então $K$ é um $TK^5$ e terminamos. Se uma das árvores $T_{x}$ não é um $TK_{1,4}$, então ele tem exatamente dois vértices de grau $3$. Contraindo $V_{x}$ sobre esses dois vértices e todos os outros ramos definidos para um único vértice, obtemos um gráfico em $6$ vértices contendo um $K_{3,3}$. Assim, $G \succeq K_{3,3}$ como desejado. Se cada uma das cinco árvores $T_{x}$ é um $TK_{1,4}$, então $K$ é um $TK^5$ e terminamos. Se uma das árvores $T_{x}$ não é um $TK_{1,4}$, então ele tem exatamente dois vértices de grau $3$. Contraindo $V_{x}$ sobre esses dois vértices e todos os outros ramos definidos para um único vértice, obtemos um gráfico em $6$ vértices contendo um $K_{3,3}$. Assim, $G \succeq K_{3,3}$ como desejado.
  
 +<wrap right>$\square$</wrap>
 </WRAP> </WRAP>
  
Linha 65: Linha 68:
  
 Fixe $i$ de forma que $Y \subseteq P_{i}$. O conjunto $C \setminus P_{i}$ está contido em uma das duas faces do ciclo $C_{i} := xx_{i}P_{i}x_{i+1}x$; denotamos a outra face de $C_{i}$ por $f_{i}$. Como $f_{i}$ contém pontos de $f$ (perto de $x$), mas nenhum ponto de seu limite $C$, temos $f_{i} \subseteq f$. Além disso, as arestas planas $xx_{j}$ com $j \not \in \{i,i+1\}$ encontram $C_{i}$ somente em $x$ e terminam fora de $f_{i}$ em $C \setminus P_{i}$, então $f_{i}$ não encontra nenhuma dessas arestas. Portanto, $f_{i} \subseteq \mathbb{R}^2 \setminus \tilde{G'}$, isto é, $f_{i}$ está contido em (e, portanto, igual a) uma face de $\tilde{G'}$. Podemos, portanto, estender $\tilde{G'}$ a um desenho de $G$ colocando $y$ e suas arestas incidentes em $f_{i}$. Fixe $i$ de forma que $Y \subseteq P_{i}$. O conjunto $C \setminus P_{i}$ está contido em uma das duas faces do ciclo $C_{i} := xx_{i}P_{i}x_{i+1}x$; denotamos a outra face de $C_{i}$ por $f_{i}$. Como $f_{i}$ contém pontos de $f$ (perto de $x$), mas nenhum ponto de seu limite $C$, temos $f_{i} \subseteq f$. Além disso, as arestas planas $xx_{j}$ com $j \not \in \{i,i+1\}$ encontram $C_{i}$ somente em $x$ e terminam fora de $f_{i}$ em $C \setminus P_{i}$, então $f_{i}$ não encontra nenhuma dessas arestas. Portanto, $f_{i} \subseteq \mathbb{R}^2 \setminus \tilde{G'}$, isto é, $f_{i}$ está contido em (e, portanto, igual a) uma face de $\tilde{G'}$. Podemos, portanto, estender $\tilde{G'}$ a um desenho de $G$ colocando $y$ e suas arestas incidentes em $f_{i}$.
 +
 +<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. 102-104. Acesso em 20/04/2023.
  
 </WRAP> </WRAP>
  • grafos/graphplanar.1681995636.txt.gz
  • Última modificação: 2023/04/20 10:00
  • por piva