Diferenças

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

--- grafos:numerdecores [2023/05/10 12:24] – piva
+++ grafos:numerdecores [2023/06/12 14:13] (atual) – edição externa 127.0.0.1
@@ Linha 12: / Linha 12: @@
 onde:
-  * $\chi(G)$ é a [[.coloracao | coloração de G]]
+  * $\chi(G)$ é a [[.coloracao | número cromático (vertice) de $G$]].
 </WRAP>
-Dem 1:
-Vamos visualizar que se temos 1,2 e 3 componentes conexas como na imagem a seguir
+<WRAP round box 100%>
+//**Demonstração:**//
+Seja $\mathcal{c}$ uma coloração de vértice de $G$ com $k=\chi(G)$ cores. Então $G$ tem pelo menos uma aresta entre quaisquer duas classes de cores: caso contrário, poderíamos ter usado a mesma cor para ambas as classes.
+Se, por exemplo, temos $1,2$ e $3$ componentes conexas como na imagem a seguir:
 {{:grafos:tri.jpg?400|}}
-é uma 3-coloração, contudo se não existisse a aresta 1-2, então poderíamos trocar a cor do 2 para a cor do 1, ou vice versa, tendo assim uma 2 coloração.
+Vemos que a situação é uma $3$-coloração, contudo se não existisse a aresta $1-2$, então poderíamos trocar a cor do $2$ para a cor do $1$, ou vice versa, tendo assim uma $2$-coloração.
 Dessa forma o número de arestas $m$ de um grafo $G$, possui a seguinte relação:
@@ Linha 27: / Linha 31: @@
 $$m \geq \binom{k}{2} = \frac{k(k-1)}{2}$$
-Assim podemos calcular a raiz da equação:
+Assim, resolvendo para $k$, podemos calcular a raiz da equação:
-   * $K \leq \frac{1}{2} + \sqrt{\frac{1}{4} + 2m}$ <wrap right>$\square$</wrap>
-----
-Dem 2:
-Seja C uma coloração de vértice de G com K cores. Então G tem pelo menos uma aresta entre quaisquer duas classes de cores: caso contrário, poderíamos ter usado a mesma cor para ambas as classes. Assim, M. Resolvendo esta desigualdade para K, obtemos a afirmação reivindicada.
+$$k \leq \frac{1}{2} + \sqrt{2m + \frac{1}{4}}$$
+<wrap right>$\square$</wrap>
+</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. 122. Acesso em 12/06/2023.
+</WRAP>