grafos:alggul [WikiMat]

Essa página está em modo somente de leitura. Você pode visualizar a fonte, mas não alterá-la. Informe-se com o administrador do Wiki, caso você ache que isso está incorreto.
==== Algorítmo guloso e $col(G)$ ====

Uma maneira óbvia de colorir um grafo $G$ com poucas cores é o seguinte //**algoritmo guloso**//: começando de uma enumeração fixa $v_1, \dots, v_n$ de $G$, consideramos os vértices por sua vez e colorimos cada $v_i$ com as primeiras cores disponíveis, ou seja, com o menor valor positivo inteiro ainda não usado para colorir qualquer vizinho de $v_i$ entre $v_1, \dots, v_{i-1}$. Desta forma, nunca usamos mais que $\Delta (G)+1$ cores, mesmo para escolhas desfavoráveis da enumeração $v_1, \dots, v_n$. Se $G$ for completo ou um ciclo ímpar, então isso é ainda melhor possível.

Em geral, este limite superior de $\Delta (G)+1$ é bastante generoso mesmo para colorações gulosas. De fato, quando vamos colorir o vértice $v_i$ no algoritmo acima, precisamos apenas de um suprimento de cores $d_{G[v_1, \dots, v_i]}(v_i)+1$ em vez de $d_{G}(v_i)+1$ para prosseguir; lembre-se que, neste estágio, o algoritmo ignora quaisquer vizinhos $v_j$ de $v_i$ com $j >i$. Portanto, na maioria dos grafos, haverá espaço para uma melhoria do limite $\Delta +1$, escolhendo uma ordem de vértice particularmente adequada para começar: uma que escolha os vértices de alto grau no início (quando a maioria dos vizinhos é ignorada) e os vértices de pequeno grau por último. Localmente, o número $d_{G[v_1, \dots, v_i]}(v_i)+1$ de cores necessárias será menor se $v_i$ tiver grau mínimo em $G[v_1, \dots, v_i]$. Mas isso é facilmente alcançado: basta escolher $v_n$ primeiro, com $d(v_n) = \delta (G)$, depois escolher como $v_{n-1}$ um vértice de grau mínimo em $G-v_n$ , e assim por diante.

O último número $k$ tal que $G$ tem uma enumeração de vértice na qual cada vértice é precedido por menos de $k$ de seus vizinhos é chamado de **//número de coloração//** $col(H)$ de $G$. A enumeração que acabamos de discutir mostra que $col(G) \leq max_{H \subseteq G} \delta (H) +1$. Mas para $H \subseteq G$ claramente também $col(G) \geq col(H)$ e $col(H) \geq \delta (H)+1$, já que o grau anterior do último vértice em qualquer enumeração de $H$ é apenas seu grau comum em $H$, que é pelo menos $\delta (H)$. Portanto, provamos o seguinte:

<WRAP round box 100%>
=== Proposição ===
//Todo grafo $G$ satifaz//

$$\chi(G) \leq col(G)=max\{\delta (H) \mid H \subseteq G\}+1$$

</WRAP>

**Observação:** O número de cores do grafo está próximo de sua arboricidade; veja o [[grafos:arboricitypacking#teorema_da_cobertura_nash-williams_1964|Teorema de Nash-Williams]]. 















-----
Para realizarmos uma coloração precisamos escolher um determinado método para ela, para isso começaremos escolhendo um vértice e criaremos uma sequência a partir dele , dessa forma iremos colorir cada $v_i$ em ordem, com isso $k \leq$ [[.grauMaximo| $\Delta(G)$]] + 1.

  * Para melhorar tal algorítmo iremos procurar por uma ordenação que diminua o número de cores, assim optaremos por escolher os vértices de grau maior antes, de maneira que o último vértice obedeça $\delta(v_n) = $ [[.grauMinimo| $\delta(G)$]] e [[.grauV| $d(v_{n-1})$]] $= \delta(G \setminus v_n)$ e assim por diante.
  * Assim $Col(G)$ é o menor $k$ tal que existe uma ordem sobre $G$ que todo $v$ possui menos que $k$ adjacentes de grau menor.

----

<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-123. Acesso em 12/06/2023.

</WRAP>