Classes de problemas

Questões-guia:

1. Conhece-se um algoritmo polinomial para algum problema NP-completo?  Pode-se dizer que não há algoritmo polinomial para um problema NP-completo?
2. Às vezes dois problemas com enunciados semelhantes podem ser: um deles polinomial e o outro NP-completo.  Dê exemplos.
3. O que são as classes P e NP?  É verdade que P ⊆ NP?  É verdade que NP ⊆ P?
4. O que é a classe NPC?  Ela é diferente de NP?
5. Quais são os principais elementos para mostrar que um problema é NP-completo?
6. O que são problemas de decisão?  Qual sua relação com problemas de otimização?
7. O que é uma redução de um problema A para um problema B?
8. Porque precisamos de um primeiro problema NP-completo?

Exercícios:

1. Ache um problema de decisão intimamente relacionado ao problema do ciclo hamiltoniano.
2. Ache um problema de decisão intimamente relacionado ao problema de coloração de grafos.
3. O problema de saber se P=NP é um dos grandes desafios da computação contemporânea.  Qual o valor que o Instituto Clay se comprometeu a pagar ao primeiro que resolver esta questão?

Coloração de arestas

Questões-guia:

1. Como emparceirar n equipes que estejam disputando um campeonato de todos contra todos?  Quantas rodadas são necessárias?
2. Defina os seguintes termos: k-aresta-coloração, coloração própria de arestas, grafo k-aresta-colorável, índice cromático.
3. Para grafos simples G, o que pode dizer sobre a relação entre o índice cromático χ'(G) e o grau máximo Δ(G)?
4. O que é um grafo "classe 1"?  E um grafo "classe 2"?
5. A que classe pertencem os grafos bipartidos?
6. Qual a relação entre χ'(G) e Δ(G) em grafos com arestas múltiplas?
7.  O que é um grafo overfull (transbordante?)  A que classe tais grafos pertencem?
8. O que diz o Teorema de Vizing e quais os elementos principais de sua prova?  Consulte, além do livro de West, adotado nesta disiplina, um paper interessante de Misra e Gries sobre o assunto, publicado em 1990.

Exercícios:

1. Exercício 7.1.1 do West, apenas χ'(G).
2. Calcule o número de 3-aresta-colorações próprias de K_3,3.
3. Mostre um grafo G e uma escolha de emparelhamentos máximos tais que o algoritmo a seguir NÃO forneça o índice cromático de G.
   

Teorema das 4 cores

Questões-guia:

1. Porque todo grafo planar simples tem pelo menos um vértice com grau até 5?
2. Com base na questão 1, como colorir os vértices de um grafo planar usando no máximo 6 cores?
3. Como fazer para incrementar um pouco este algoritmo, através de contrações, e usar no máximo 5 cores?  Veja dicas no nosso texto auxiliar de Tarjan e colegas (1980).  Cuidado, pois há vários errinhos tipográficos neste texto.  Deve ter sido digitalizado por OCR.
4. O próximo passo seria provar que 4 cores bastam, mas isto ainda é muito difícil.  Vejamos então alguns marcos desta história:

• 1852: O que de Morgan escreveu a Hamilton nesta data?
• 1878: O que Tait provou nesta data?
• 1879: O que Kemper publicou nesta data?
• 1890: O que fez Headwood nesta data?
• 1946: Que contra-exemplo importante surgiu nesta data?
• 1968: O que Grinberg mostrou nesta data?
• 1976: O que Appel e Haken apresentaram nesta data?
• 1986: O que Appel e Haken apresentaram nesta data?
• 1996: O que Robertson, Sanders, Seymour e Thomas apresentaram nesta data?

Exercícios:

1. É verdade que sempre haverá um emparelhamento perfeito no dual de uma triangulação?
2. Ex. 7.3.14 do West.
3. Ex. 7.3.17 do West.

Planaridade

Questões-guia:

1. Como é o problema de gás-água-eletricidade?  Ele tem solução?  E se fossem 5 vizinhos querendo se conectar todos com todos?
2. O que é uma curva?  E uma curva poligonal?  O que é um desenho?  O que é um cruzamento num desenho?
3. Qual a diferença entre um grafo plano e um grafo planar?  O que é uma curva fechada?  E uma curva simples?
4. O que é um conjunto aberto?  E uma região?  O que são as faces de um grafo plano?  O que é a façe externa de um grafo plano?  Só há uma face externa num grafo plano?
5. Como se constrói o dual G* de um grafo plano G?  Dê exemplos.
6. O que é o comprimento de uma face?  A que corresponde no dual?  O que é um grafo periplanar (outerplanar)?
7. O que diz a Fórmula de Euler para grafos planos conexos?  Como se pode generalizá-la para grafos planos desconexos?
8. Um grafo simples pode ter um número quadrático de arestas, em relação ao número de vértices.  Isto pode acontecer com grafos planares simples?  Por quê?
9. O que é uma triangulação?  Quais são todos os grafos planares simples, regulares e cujo dual também é regular?  Desenhe-os no plano.  Quais deles são triangulações?

Exercícios:

1. Ex. 6.1.2 do West.
2. Ex. 6.1.14 do West.
3. Ex. 6.2.4 do West.

Coloração de vértices

Questões-guia:

1. Defina os seguintes termos: k-coloração; coloração própria; grafo k-colorável; grafo k-partido; número cromático χ(G) de um grafo G.  Dê exemplos.
2. Defina os seguintes termos: grafo k-cromático; coloração ótima; grafo k-crítico.  Dê exemplos.
3. É fácil ou difícil saber se um grafo é 2-colorável?  E 3-colorável?
4. O que é ω(G)?  Qual a relação entre ω(G) e χ(G)?
5. O grau máximo de uma grafo G é denotado por Δ(G).  Qual a relação entre Δ(G) e χ(G)?  Para quais grafos temos χ(G) = Δ(G)+1?
6. Qual é o mínimo número de arestas para um grafo com n vértices e número cromático k?  E o máximo?
7. O que é o polinômio cromático de um grafo?  Qual seria a complexidade de um algoritmo para calculá-lo com base no Teorema 5.3.6?
8. O que é um grafo cordal?  Qual a importância de grafos cordais no estudo do número cromático?

Exercícios:

1. Ex. 5.1.7 do West.
2. Ex. 5.1.29 do West.
3. Implementar MCS (algoritmo 8.1.12 do West) com LEMON.  Faça seu programa receber na linha de comando o grafo em LGF.  Aplique no grafo do exemplo 8.1.13.

Fluxos em redes

Questões-guia:

1. Problemas de fluxo máximo são estudados em certos tipos especiais de grafos chamados redes.  O que é uma rede?  O que é um fluxo numa rede?  Como se define o valor de um fluxo?
2. Cormen evita arestas antiparalelas no grafo inicial, e explica como eliminá-las.  Uma abordagem alternativa, que permite arestas antiparalelas no grafo inicial, é dada por Goldberg e Tarjan num artigo de 1988.  Quais as diferenças entre as duas abordagens?
3. O que é a rede residual?  Ela tem arestas antiparalelas?  Curiosidade: como se relacionam o fluxo máximo no grafo inicial com o fluxo máximo na rede residual?
4. O que é um caminho aumentante numa rede residual?  Como ele é usado no método de Ford-Fulkerson?
5. O que é um corte numa rede?  Como se define sua capacidade?  Qual a relação entre capacidades de cortes e valores de fluxos?
6. O que diz o teorema Max-Flow Min-Cut?  Como encontrar um corte mínimo numa rede residual sem caminho aumentante?
7. Como funciona o algoritmo de Edmonds-Karp?  Qual é sua complexidade?
8. Como se pode reduzir o problema de achar um emparelhamento máximo num grafo bipartido ao problema de fluxo máximo?  Onde entra o teorema da integralidade nesta redução?

Exercícios:

1. Rode um algoritmo de fluxo máximo do LEMON na rede dada na Figura 26.1 do Cormen.  O valor do fluxo deu igual ao do livro?  Qual foi o corte mínimo retornado pelo algoritmo?
2. Rode um algoritmo de fluxo máximo do LEMON na rede dada na Figura 26.3b do Cormen.  Como você codificou as capacidades infinitas?  Quanto deu o fluxo máximo?
3. Use um algoritmo de fluxo máximo do LEMON para achar um emparelhamento de cardinalidade máxima no grafo bipartido da Figura 26.8a do Cormen.

Caminhos mínimos

Questões-guia:

1. O que é o problema de passeios mínimos de fonte fixa num grafo orientado ponderado?
2. Vamos estudar também o problema com fonte e destino fixos?  Por quê?
3. O que é sub-estrutura ótima?  O problema de passeios mínimos tem esta propriedade?  De que forma?
4. O que ocorre se o grafo tiver ciclos negativos?  E se tiver arestas negativas, mas não ciclos negativos?  Qual a relação entre passeios mínimos e caminhos mínimos?
5. Qual é a saída típica de um algoritmo para resolver o problema de caminhos mínimos?
6. Segundo Cormen, o que são a inicialização e o relaxamento?  Por que o relaxamento tem este nome?
7. Quais as 6 propriedades fundamentais de algoritmos que usam a inicialização de Cormen e modificam as estimativas de caminhos mínimos apenas através de passos de relaxamento?
8. Faça um diagrama JSP do algoritmo de Bellman-Ford.  Tente usar não mais que 10 caixas.  Permite arestas negativas?  Ciclos negativos?  Há restrições à estrutura do grafo?  Qual sua complexidade?
9. Faça um diagrama JSP do algoritmo para caminhos mínimos num DAG.  Tente usar não mais que 7 caixas.  Permite arestas negativas?  Ciclos negativos?  Há restrições à estrutura do grafo?  Qual sua complexidade?
10. Faça um diagrama JSP do algoritmo de Dijkstra.  Tente usar não mais que 8 caixas.  Permite arestas negativas?  Ciclos negativos?  Há restrições à estrutura do grafo?  Qual sua complexidade?

Exercícios:

ATENÇÃO: ao testar os programas nos grafos, não construa os grafos no código.  Faça um arquivo LGF para o grafo e leia este arquivo no código.

1. Implemente Bellman-Ford em LEMON, seguindo um bom esquema JSP.  Teste com o exemplo da Figura 24.4.  A seguir, modifique o exemplo para conter um ciclo negativo, e teste novamente.
2. Implemente DAG-SHORTEST-PATHS em LEMON, seguindo um bom esquema JSP.  Teste com o exemplo da Figura 24.5.
3. LEMON já tem uma implementação de Dijsktra.  Teste com o exemplo da Figura 24.6.