Projeto e Análise de Algoritmos I

Aula 26 - Coloração de Grafos

Lucas Nunes Alegre

Universidade Federal do Rio Grande do Sul
Instituto de Informática
Departamento de Informática Teórica

Estes slides utilizam conteúdo adaptado da bibliografia da disciplina e também de notas de aula e slides prévios dos professores Bruno Grisci, Rodrigo Machado e André Grahl.

Motivação e Aplicações

Colorindo um Mapa

Vamos colorir os países da América do Sul de modo que países vizinhos tenham cores diferentes.

Começamos pelo Brasil: verde.

Argentina: azul. O Uruguai é vizinho dos dois: precisamos de uma terceira cor.

Uruguai: amarelo.

Chile e Paraguai: amarelo. A Bolívia é vizinha de Brasil, Argentina, Chile e Paraguai: não pode ser verde, amarelo nem azul!

Bolívia: vermelho, a quarta cor.

Peru: azul.

E assim por diante, até o último país.

Do Mapa ao Grafo

Nodos: países.
Arestas: países que fazem fronteira.
Cores: cores do mapa.

Como no dual planar (aula passada), o grafo de um mapa é planar.

Foram necessárias 4 cores para colorir a América do Sul.

Nesta aula: todo grafo planar (e.g., mapas) pode ser colorido com 4 cores!

Agendamento de Provas

Disciplinas: Teoria dos Grafos, Estruturas de Dados, ARQ I, Lógica e Cálculo II.
Professores querem agendar as datas das provas.
Restrição: nenhum aluno com mais de uma prova no mesmo dia.
Qual o menor número de dias de provas necessário?

	Bob	Alice	João	Maria
Grafos	x		x
E.D.	x	x		x
Cálculo II				x
ARQ I			x
Lógica		x

Provas que cada aluno precisa realizar.

Nodos: disciplinas. Arestas: disciplinas com algum aluno em comum (Bob faz Grafos e E.D.).

Alice, João e Maria geram as demais arestas.

Dia 1: Grafos, Cálculo II e Lógica.

Dia 2: ARQ I e E.D. Cores: dias. Bastam 2 dias!

Sudoku

Sudoku 4 \times 4: cada linha, coluna e bloco 2 \times 2 deve conter os valores de 1 a 4.

Nodos: células do jogo.
Arestas: células na mesma linha, coluna ou bloco (restrições).
Cores: valores de 1 a 4.

Resolver o Sudoku é completar uma 4-coloração parcial do grafo! (No Sudoku 9 \times 9: 81 nodos e 9 cores.)

Alocação de Registradores

Considere o programa abaixo, com variáveis a, \ldots, e e 3 registradores: R_1, R_2, R_3.
Como alocar as variáveis em registradores de modo a evitar conflitos temporais?
Nodos: variáveis. Arestas: variáveis em uso ao mesmo tempo. Cores: registradores.

R1: a, d, e
R2: b
R3: c

Frequências de Torres de Rádio

Problema: alocar frequências para torres de rádio.
Restrição: evitar interferência de sinal entre torres próximas.
Nodos: torres. Arestas: torres próximas o suficiente para interferir. Cores: frequências.

Coloração de Grafos

Definição: Seja G=(V,E) um grafo simples. Uma coloração (de vértices) de G é uma função f: V \to C tal que, para todo u, v \in V,

\{u,v\} \in E \Rightarrow f(u) \neq f(v)

onde C \subseteq \mathbb{N} é o conjunto de cores.

Exemplo:

|img(f)| = 3

Definição: |img(f)| é o número de cores da coloração f.

Grafos k-Coloríveis

Definição: Um grafo G é k-colorível sss existe uma coloração de G com no máximo k cores.

Exemplo: o grafo do slide anterior é 3-colorível (e também 4-colorível, 5-colorível, …).

Mas ele não é 2-colorível: B, C e D formam um triângulo, e cada um precisa de uma cor diferente.

Importante: pseudografos com laços não são coloríveis: um laço \{v, v\} exigiria f(v) \neq f(v).

Número Cromático

Definição: O número cromático \chi(G) de um grafo G é o menor número de cores k tal que G é k-colorível.

G \text{ é } k\text{-cromático} \iff \chi(G) = k

Grafo de Petersen

Exemplo:

10-colorível

9-colorível

\ldots

3-colorível

não é 2-colorível: o ciclo externo tem 5 vértices (ciclo ímpar).

\Rightarrow 3-cromático: \chi(G) = 3.

Número Cromático: Exercício

Exercício: Determine o número cromático dos grafos abaixo. (Clique nos vértices para colori-los.)

Limites para o Número Cromático

Limites Triviais

Seja \chi(G) o número cromático de um grafo simples G = (V, E).

Se |V| = 0, então \chi(G) = 0.

Se |E| = 0 e |V| > 0, então \chi(G) = 1.

Para qualquer G: \chi(G) \leq |V| (basta dar uma cor diferente para cada vértice).

Limites: Partições e Cliques

Se G é bipartido, então \chi(G) \leq 2.

Mais geralmente: se G é k-partido, então \chi(G) \leq k (uma cor para cada parte).

Seja \omega(G) o tamanho do maior clique de G. Então \chi(G) \geq \omega(G).
- Em um clique, cada vértice deve obrigatoriamente ter uma cor diferente.

\chi(K_5) = 5

Limite Superior: \chi(G) \leq \Delta(G) + 1

Teorema: Seja G = (V, E) um grafo simples, onde \Delta(G) é o maior grau de algum vértice em V. Então

\chi(G) \leq \Delta(G) + 1.

Ideia: Se um vértice u possui d vizinhos, então mesmo que cada vizinho tenha uma cor diferente, basta uma cor adicional para u (d + 1 cores). Como d \leq \Delta(G) para todo vértice, \Delta(G) + 1 cores são suficientes.

Nota: O limite é justo: \chi(K_n) = n = \Delta(K_n) + 1. (Teorema de Brooks: grafos completos e ciclos ímpares são os únicos grafos conexos que o atingem.)

Limite Superior: Demonstração

Demonstração:

Seja v_1, v_2, \ldots, v_n uma permutação arbitrária dos vértices em V.
Seja C = \{c_1, \ldots, c_k\} um conjunto de k = \Delta(G) + 1 cores.

Colorindo v_i (em ordem): atribua a primeira cor não usada em nenhum vizinho já colorido.

Pior caso: há \Delta(G) vizinhos de v_i já coloridos, todos com cores diferentes.

Portanto, precisamos de uma cor adicional: no máximo \Delta(G) + 1 cores. \blacksquare

\Delta(G) = 3
k = \Delta(G) + 1 = 4

Nota: este procedimento é exatamente o algoritmo guloso, que veremos no final da aula.

Coloração de Grafos Planares

Coloração e Grafos Planares

Restringindo nossa atenção a grafos planares, obtemos resultados mais precisos.

Conjectura das 4 Cores: é sempre possível colorir um mapa usando apenas 4 cores.
- Postulada em 1852 por Francis Guthrie, ao colorir o mapa dos condados da Inglaterra.

Vamos começar por um resultado mais fraco (e com prova bem mais simples): o Teorema das 5 Cores.

Teorema das 5 Cores: Lema

Teorema: (5 Cores) Se G = (V, E) é simples e planar, então \chi(G) \leq 5.

Lema: Seja G = (V, E) um grafo simples e planar. Então existe pelo menos um vértice v com no máximo 5 vizinhos.

Demonstração: Por contradição. Assuma que todo vértice v tem pelo menos 6 vizinhos.

Pelo corolário da fórmula de Euler (aula passada), temos |E| \leq 3|V| - 6
Porém, se todo vértice tem pelo menos 6 vizinhos, como \sum_{v} deg(v) = 2|E| (handshake lemma): 2|E| \geq 6|V| \quad \Rightarrow \quad |E| \geq 3|V|
Contradição! Teríamos 3|V| \leq |E| \leq 3|V| - 6. \blacksquare

Teorema das 5 Cores: Indução

Teorema: (5 Cores) Se G = (V, E) é simples e planar, então \chi(G) \leq 5.

Demonstração: Por indução no número de vértices n.

Proposição P(n): Se G é simples, planar e possui n vértices, então \chi(G) \leq 5.

Caso base: P(n) para n \leq 5. Trivial: cada vértice pode receber uma cor diferente.

Hipótese de indução: P(k) vale para todo k < n, isto é, todo grafo simples e planar com k < n vértices tem \chi \leq 5.

Passo: vamos demonstrar que P(k < n) \to P(n). Seja G simples e planar com n vértices. Pelo lema, existe um vértice v com no máximo 5 vizinhos. Dois casos:

Caso 1: v tem no máximo 4 vizinhos.
Caso 2: v tem exatamente 5 vizinhos.

Teorema das 5 Cores: Caso 1

Caso 1: v tem no máximo 4 vizinhos.

1. Ao remover v, G - v tem n - 1 vértices (e continua simples e planar).

2. Pela H.I., P(n-1): G - v é 5-colorível.

3. Ao reintroduzir v: seus (no máximo) 4 vizinhos usam no máximo 4 cores, então sobra uma cor.

4. Colorimos v com a cor restante! Logo, P(n-1) \to P(n).

Teorema das 5 Cores: Caso 2

Caso 2: v tem exatamente 5 vizinhos, e em G - v (colorido pela H.I.) eles usam 5 cores diferentes. (Se usassem 4 ou menos, sobraria uma cor, como no caso 1.)

1. Entre os vizinhos v_1, \ldots, v_5, deve haver dois não-adjacentes (senão teríamos K_5, que não é planar). Sejam v_2 e v_5.

2. Contraímos as arestas \{v, v_2\} e \{v, v_5\}: o grafo resultante é simples, planar e tem n - 2 vértices.

3. Pela H.I., ele é 5-colorível.

4. Desfazendo a contração (ainda sem v), v_2 e v_5 ficam com a mesma cor.

5. Ao reintroduzir v, seus 5 vizinhos usam no máximo 4 cores: sobra uma cor para v! Logo, P(k < n) \to P(n). \blacksquare

Teorema das 4 Cores

Teorema: Se G = (V, E) é simples e planar, então \chi(G) \leq 4.

Conhecido como Four Color Theorem (Teorema das Quatro Cores).

1852: Francis Guthrie formula a conjectura; seu irmão Frederick a leva ao professor Augustus De Morgan.

1879: Alfred B. Kempe anuncia uma demonstração da conjectura. Ganhou muito prestígio e foi eleito membro da Royal Society.

1890: Percy Heawood encontra um erro na prova de Kempe e, a partir dela, prova o Teorema das 5 Cores.

Augustus De Morgan (1806–1871)

Teorema das 4 Cores: A Prova

Teorema: Se G = (V, E) é simples e planar, então \chi(G) \leq 4.

Somente em 1976, Appel & Haken provaram o teorema com ajuda de computadores.
Primeira vez que um teorema importante é provado dessa forma!

Ideia: reduzir o problema a 1936 configurações e testá-las por computador, usando ~1200 horas de computação!
À mão, estima-se que levariam 100 mil anos, dedicando-se 60h/semana.

A prova foi simplificada desde então, mas, até hoje, não existe prova do teorema sem auxílio de computadores.

Algumas das configurações da prova de Appel & Haken.

Teorema das 4 Cores: Repercussão

Muitos questionaram a legitimidade da prova.
- O que conta como uma prova válida?

Computadores se tornaram ubíquos em provas matemáticas: em 2005, a prova foi verificada formalmente no assistente de provas Coq.

Propulsor do estudo de Teoria dos Grafos ao longo do tempo.

Kenneth Appel e Wolfgang Haken.

Algoritmos de Coloração

Algoritmos de Coloração: Complexidade

Como computar \chi(G) dado um grafo G?
- Problema NP-Difícil!

Como verificar se G é k-colorível, isto é, se \chi(G) \leq k?
- Problema NP-Completo! (Um dos 21 problemas NP-Completos de Karp.)

Disciplina de Teoria da Computação II
Classes de complexidade computacional

Intuitivamente: até onde se sabe, o número de operações para resolver o problema cresce exponencialmente com o tamanho do grafo.

Algoritmos de Coloração: Casos Tratáveis

Decidir se um grafo é 2-colorível \iff testar bipartição.
- Pode ser feito em tempo linear usando BFS ou DFS.
Existem fórmulas fechadas para o polinômio cromático P(G, k) (o número de colorações de G com até k cores) de:
- florestas, grafos cordais, ciclos, rodas, escadas.
Grafos com baixa branch-width (dada uma decomposição em ramos):
- Resolvíveis em tempo polinomial no tamanho do grafo via programação dinâmica;
- Mas exponencial na largura da decomposição.

Curiosidade: todo grafo planar tem uma 4-coloração, que pode ser encontrada em tempo O(n^2); mas decidir se um grafo planar é 3-colorível continua NP-Completo!

Algoritmos de Coloração Exatos

Busca exaustiva para k cores: testar todas as k^n \text{ atribuições}
- Verificar cada atribuição \to impraticável para n moderado. Ex.: 3^{50} \approx 7{,}2 \times 10^{23}.
- Para obter o número cromático, é necessário repetir para k = 1, \ldots, n - 1.

Programação dinâmica e limites no número de conjuntos independentes maximais: k-colorabilidade em O(2{,}4423^n).
Inclusão–exclusão: k-colorabilidade em O(2^n \, n), para qualquer k.

Algoritmos mais rápidos para casos específicos:
- 3-colorabilidade: O(1{,}3289^n); 4-colorabilidade: O(1{,}7272^n).
- 5 e 6 cores: também há algoritmos exponencialmente mais rápidos que o caso geral.
Melhorias também para famílias restritas (ex.: grafos esparsos).

Algoritmo Guloso (Não Ótimo)

Entrada: grafo simples G = (V, E) e cores C = \{c_1, c_2, \ldots, c_k\}.
Saída: coloração f: V \to C.

\begin{algorithmic} \Procedure{ColoracaoGulosa}{$G=(V,E)$, $C$} \State Ordene os vértices $v_1, v_2, \ldots, v_n$ em ordem arbitrária. \For{$i = 1$ até $n$} \State $j \gets 1$ \While{algum vizinho de $v_i$ possui cor $c_j$} \State $j \gets j + 1$ \Comment{vá para a próxima cor} \EndWhile \State $f(v_i) \gets c_j$ \EndFor \State \textbf{Retorne} $f$ \EndProcedure \end{algorithmic}

Com k = \Delta(G) + 1 cores, sempre há uma cor disponível (teorema anterior).
Fixada a ordem, pode ser implementado em O(|V| + |E|).

Algoritmo Guloso: Exemplo

Cores, em ordem: \textcolor{#1565c0}{\mathbf{c_1}}, \textcolor{#c62828}{\mathbf{c_2}}, \textcolor{#2e7d32}{\mathbf{c_3}}, \textcolor{#c17900}{\mathbf{c_4}}. Ordem dos vértices: v_1, v_2, \ldots, v_6.

v_1: nenhum vizinho colorido \to \textcolor{#1565c0}{\mathbf{c_1}}

v_2: vizinho com c_1 \to \textcolor{#c62828}{\mathbf{c_2}}

v_3: vizinho com c_2 \to \textcolor{#1565c0}{\mathbf{c_1}}

v_4: vizinhos com c_1, c_2 \to \textcolor{#2e7d32}{\mathbf{c_3}}

v_5: vizinhos com c_1, c_2, c_3 \to \textcolor{#c17900}{\mathbf{c_4}}

v_6: vizinhos com c_1, c_4 \to \textcolor{#c62828}{\mathbf{c_2}}

O guloso usou 4 cores, mas \chi(G) = 3! Com a ordem v_2, v_6, v_4, v_3, v_1, v_5, ele usa apenas 3.

Algoritmo Guloso: Qualidade

Sempre existe uma ordem de vértices que produz uma coloração ótima (com \chi(G) cores) usando o método guloso.
Por outro lado, o método pode ser arbitrariamente ruim:
Exemplo: crown graph com n vértices (u_i adjacente a w_j sss i \neq j):
- É 2-colorível;
- Mas existe uma ordem que faz o guloso usar n/2 cores.
Moral: a ordem dos vértices é crucial.

2 cores

n/2 = 4 cores

Os rótulos indicam a ordem em que o guloso visita os vértices.

Heurística de Welsh–Powell

Ideia: ordenar os vértices por grau decrescente: x_1, x_2, \ldots, x_n.
Aplicar a coloração gulosa nessa ordem.
Garante usar no máximo \max_i \, \min\{deg(x_i) + 1,\ i\} \text{ cores.}
Em particular: usa no máximo \Delta(G) + 1 cores (no máximo um a mais que o grau máximo).
Simples, rápido e muito usado na prática.

Exemplo: no grafo anterior, a ordem por grau é v_2, v_5 (grau 4), v_3, v_4 (grau 3), v_1, v_6 (grau 2).

O guloso nessa ordem usa 3 cores: ótimo!