Diferenças

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

--- grafos:colouringintro [2023/05/07 21:11] – edição externa 127.0.0.1
+++ grafos:colouringintro [2023/06/11 14:03] (atual) – edição externa 127.0.0.1
@@ Linha 5: / Linha 5: @@
 Uma **//coloração de vértice//** de um grafo $G=(V,E)$ é um mapa $\mathcal{c} : V \to S$ tal que $\mathcal{c}(v) \neq \mathcal{c}(w)$ sempre que $v$ e $w$ são adjacentes. Os elementos do conjunto $S$ são chamados de **cores** disponíveis. Tudo o que nos interessa sobre $S$ é o seu tamanho: tipicamente, estaremos pedindo o menor inteiro $k$ tal que $G$ tenha uma **$k$-coloração** , um vértice colorindo $\mathcal{c} : V \to \{1,\dots, k\}$. Este $k$ é o **(vértice-)número cromático** de $G$; é denotado por $\chi(G)$. Um grafo $G$ com $\chi(G)=k$ é chamado **$k$-cromático**; se $\chi(G) \leq k$, chamamos $G$ **$k$-colorível**.
-Um vértice colorindo $V \to \{1,\dots\4\}$:
+Um vértice colorindo $V \to \{1,\dots,4\}$:
 {{ :grafos:graph303.png?300 |}}
-Observe que uma k-coloração nada mais é do que uma partição de vértices em K conjuntos independentes, agora chamados de classes de cores; os grafos 2-coloríveis não triviais, por exemplo, são precisamente os grafos bipartidos. Historicamente, a terminologia de coloração vem do problema de coloração de mapas mencionado acima, que leva ao problema de determinar o número cromático máximo de grafos planares. O problema de agendamento do comitê também pode ser formulado como um problema de coloração de vértices_ como?
+Observe que uma $k$-coloração nada mais é do que uma partição de vértices em $k$ conjuntos independentes, agora chamados de **//classes de cores//**; os grafos $2$-coloríveis não triviais, por exemplo, são precisamente os grafos bipartidos. Historicamente, a terminologia de coloração vem do problema de coloração de mapas mencionado acima, que leva ao problema de determinar o número cromático máximo de grafos planares. O problema de agendamento do comitê também pode ser formulado como um problema de coloração de vértices.
-Uma coloração de aresta de G é um mapa C com C para quaisquer arestas adjacentes E. O menor inteiro K para o qual existe uma coloração de aresta k, ou seja, uma coloração de aresta C, é o número cromático de aresta, ou índice cromático, de G ; é denotado por X. A terceira de nossas questões introdutórias pode ser modelada como um problema de coloração de arestas em um multigrafo bipartido_ como?
+Uma **coloração de aresta** de $G$ é um mapa $\mathcal{c} : E \to S$ com $\mathcal{c}(e) \neq \mathcal{c}(f)$ para quaisquer arestas adjacentes $e,f$. O menor inteiro $k$ para o qual existe uma **$k$-coloração-aresta** k, ou seja, uma coloração de aresta $\mathcal{c}: E \to \{1,\dots,k\}$, é o **número cromático de aresta**, ou **índice cromático**, de $G$; é denotado por $\chi'(G)$. A terceira de nossas questões introdutórias pode ser modelada como um problema de coloração de arestas em um multigrafo bipartido.
-Claramente, toda coloração de arestas de G é uma coloração de vértice de seu grafo de linha L, e vice-versa; em particular, X. O problema de encontrar boas colorações de arestas pode, portanto, ser visto como uma restrição do problema mais geral de coloração de vértices a essa classe especial de grafos. Como veremos, essa relação entre os dois tipos de problema de coloração é refletida por uma diferença marcante em nosso conhecimento sobre suas soluções: embora existam apenas estimativas muito aproximadas para X, seu irmão X sempre assume um dos dois valores, X ou X.
+Claramente, toda coloração de arestas de $G$ é uma coloração de vértice de seu grafo de linha $L(G)$, e vice-versa; em particular, $\chi'(G) = \chi(L(G))$. O problema de encontrar boas colorações de arestas pode, portanto, ser visto como uma restrição do problema mais geral de coloração de vértices a essa classe especial de grafos. Como veremos, essa relação entre os dois tipos de problema de coloração é refletida por uma diferença marcante em nosso conhecimento sobre suas soluções: embora existam apenas estimativas muito aproximadas para $\chi$, seu irmão $\chi'$ sempre assume um dos dois valores, $\Delta$ ou $\Delta +1$.
 ==== Mapas de coloração e Grafos planares ====
-Se algum resultado na teoria dos grafos tem a pretensão de ser conhecido pelo mundo exterior, é o seguinte teorema das quatro cores (que implica que todo mapa pode ser colorido com no máximo quatro cores):
+Se algum resultado na teoria dos grafos tem a pretensão de ser conhecido pelo mundo exterior, é o seguinte teorema das quatro cores, que implica que todo mapa pode ser colorido com no máximo quatro cores:
 <WRAP round box 100%>
 === Teorema das Quatro Cores ===
-Todo grafo planar é 4-colorível.
+//Todo grafo planar é $4$-colorível.//
 </WRAP>
-Algumas observações sobre a prova do teorema das quatro cores e sua história podem ser encontradas nas notas ao final deste capítulo. Aqui, provamos o seguinte enfraquecimento:
+----
+Entretanto, por ora, provemos o seguinte enfraquecimento:
 <WRAP round box 100%>
 === Teorema das Cinco Cores ===
-Todo grafo planar é 5-colorível.
+//Todo grafo planar é $5$-colorível.//
 </WRAP>
 <WRAP round box 100%>
-Dem.:
+//**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 53: / 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>