Diferenças

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

--- grafos:colouringintro [2023/05/08 13:03] – edição externa 127.0.0.1
+++ grafos:colouringintro [2023/06/11 14:03] (atual) – edição externa 127.0.0.1
@@ Linha 36: / Linha 36: @@
 //**Demonstração:**//
-Seja G um grafo plano com N vértices e M arestas. Assumimos indutivamente que todo grafo plano com menos de N vértices pode ser 5-colorido. Pelo Corolário 4.2.10;
+Seja $G$ um grafo plano com $n \geq 6$ vértices e $m$ arestas. Assumimos indutivamente que todo grafo plano com menos de $n$ vértices pode ser $5$-colorido. Pelo **Corolário 4.2.10**,
-seja V um vértice de grau no máximo 5. Pela hipótese de indução, o grafo H tem uma coloração de vértice C. Se C usa no máximo 4 cores para os vizinhos de V , podemos estendê-lo para uma 5-coloração de G. Suponhamos, portanto, que V tenha exatamente 5 vizinhos, e que estes tenham cores distintas.
+$$d(G) = 2m / n \leq 2(3n-6) / n <6;$$
-Seja D um disco aberto em torno de V, tão pequeno que encontre apenas aqueles cinco segmentos de borda reta de G que contém V. Vamos enumerar esses segmentos de acordo com sua posição cíclica em D como S, e seja V a borda que contém S . Sem perda de generalidade, podemos assumir que C para cada P.
+seja $v \in G$ um vértice de grau no máximo $5$. Pela hipótese de indução, o grafo $H := G-v$ tem uma coloração de vértice $\mathcal{c} : V(H) \to \{1, \dots ,5\}$. Se $\mathcal{c}$ usa no máximo $4$ cores para os vizinhos de $v$, podemos estendê-lo para uma $5$-coloração de $G$. Suponhamos, portanto, que $v$ tenha exatamente $5$ vizinhos, e que estes tenham cores distintas.
-(FIGURAAAAAA
+Seja $D$ um disco aberto em torno de $v$, tão pequeno que encontre apenas aqueles cinco segmentos de borda reta de $G$ que contém $v$. Vamos enumerar esses segmentos de acordo com sua posição cíclica em $D$ como $s_1, \dots, s_5$, e seja $vv_{i}$ a aresta que contém $s_{i} (i=1, \dots ,5)$. Sem perda de generalidade, podemos assumir que $\mathcal{c}(v_{i}) = i$ para cada $i$.
-Vamos mostrar primeiro que todo V caminho P separa V de V em H. Claramente, este é o caso se e somente se o ciclo C separa V de V em G. Provamos isso mostrando que V e V estão em faces diferentes de C.
+{{ :grafos:graph501.png?400 |}}
-Vamos pegar um ponto interno X de S em D e um ponto interno X de S em D. Então, em D, todo ponto pode ser ligado por um arco poligonal a X ou a X. Isso implica que X e X (e, portanto, também V e V) estão em diferentes faces de C: caso contrário, D encontraria apenas uma das duas faces de C, o que contradiria o fato de que V está na quarta face de ambas as faces (Teorema 4.1.1).
+Vamos mostrar primeiro que todo $v_1-v_3$ caminho $P \subseteq H-\{v_2,v_4\}$ separa $v_2$ de $v_4$ em $H$. Claramente, este é o caso se, e somente se, o ciclo $C := vv_{1}Pv_{3}v$ separa $v_2$ de $v_4$ em $G$. Provamos isso mostrando que $v_2$ e $v_4$ estão em faces diferentes de $C$.
-Dado J, seja H o subgrafo de H induzido pelos vértices coloridos J ou J. Podemos assumir que a componente C de H contendo V também contém V. De fato, se trocarmos as cores 1 e 3 em todos os vértices de C , obtemos outra 5-coloração de H; se V , então V e V são ambos coloridos 3 nesta nova coloração, e podemos atribuir a cor 1 a V. Assim, H contém um V caminho P. Como mostrado acima, P separa V de V em H. Como P, isso significa que V e V estão em componentes diferentes de H. No componente que contém V, agora trocamos as cores 2 e 4, recolorindo assim V com a cor 4. Agora V não tem mais um vizinho colorido 2, e podemos dar a ele esta cor.
+Vamos pegar um ponto interno $x_2$ de $s_2$ em $D$ e um ponto interno $x_4$ de $s_4$ em $D$. Então, em $D \setminus (s_1 \cup s_3) \subseteq \mathbb{R}^2 \setminus C$ todo ponto pode ser ligado por um arco poligonal a $x_2$ ou a $x_4$. Isso implica que $x_24 e $x_4$ (e, portanto, também $v_2$ e $v_4$) estão em diferentes faces de $C$: caso contrário, $D$ encontraria apenas uma das duas faces de $C$, o que contradiria o fato de que $v$ está na fronteira de ambas as faces **(Teorema 4.1.1)**.
+Dado $i,j \in \{1, \dots ,5\}$, seja $H_{i,j}$ o subgrafo de $H$ induzido pelos vértices coloridos $i$ ou $j$. Podemos assumir que a componente $C_1$ de $H_{1,3}$ contendo $v_1$ também contém $v_3$. De fato, se trocarmos as cores $1$ e $3$ em todos os vértices de $C_1$ , obtemos outra $5$-coloração de $H$; se $v_3 \notin C_1$ , então $v_1$ e $v_3$ são ambos coloridos $3$ nesta nova coloração, e podemos atribuir a cor $1$ a $v$. Assim, $H_{1,3}$ contém um $v_1-v_3$ caminho $P$. Como mostrado acima, $P$ separa $v_2$ de $v_44 em $H$. Como $P \cap H_{2,4} = \emptyset$, isso significa que $v_2$ e $v_4$ estão em componentes diferentes de $H_{2,4}$. No componente que contém $v_2$, agora trocamos as cores $2$ e $4$, recolorindo assim $v_2$ com a cor $4$. Agora $v$ não tem mais um vizinho colorido $2$, e podemos dar a ele esta cor.
 </WRAP>
@@ Linha 55: / Linha 57: @@
 <WRAP round box 100%>
 === Teorema de Grotzsch (1959) ===
-Todo grafo planar que não contém um triângulo é 3-colorível.
+//Todo grafo planar que não contém um triângulo é $3$-colorível.//
+</WRAP>
+----
+<WRAP round info 100%>
+=== Referências ===
+  * Reinhard Diestel. [[https://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch5.pdf|“Graph Theory”]] .5th Electronic Edition 2016, pp. 119-121. Acesso em 10/06/2023.
 </WRAP>