Diferenças

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

--- grafos:numerdecores [2023/05/10 12:30] – piva
+++ grafos:numerdecores [2023/06/12 14:13] (atual) – edição externa 127.0.0.1
@@ Linha 17: / Linha 17: @@
-Dem 1:
+<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.
-Vamos visualizar que se temos $1,2$ e $3$ componentes conexas como na imagem a seguir
+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 29: / 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>
+$$k \leq \frac{1}{2} + \sqrt{2m + \frac{1}{4}}$$
+<wrap right>$\square$</wrap>
-----
+</WRAP>
-Dem 2:
-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. Assim, $m \geq \frac{1}{2} k(k-1)$. Resolvendo esta desigualdade para $k$, obtemos a afirmação reivindicada.
 ----
+<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>