grafos:colouringintro

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:colouringintro [2023/05/08 21:59] – pivagrafos:colouringintro [2023/06/11 14:03] (atual) – edição externa 127.0.0.1
Linha 50: Linha 50:
 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)**. 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 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.+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> </WRAP>
  
Linha 57: Linha 57:
 <WRAP round box 100%> <WRAP round box 100%>
 === Teorema de Grotzsch (1959) === === 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> </WRAP>
  • grafos/colouringintro.1683593974.txt.gz
  • Última modificação: 2023/05/08 21:59
  • por piva