Teoria dos Grafos

Jorge César Abrantes de Figueiredo

Período: 2009.2

Horário: T102 e X082

Sala: BD301

Ementa: Introdução. Noções básicas: grafos orientados, não-orientados, bipartidos. Percursos em grafos. Casamentos. Subgrafos, hipergrafos, matróides e cliques. Árvores e árvores geradoras. Conectividade. Problemas de caminhos. Estabilidade e número cromático. Grafos planares. Circuitos Eulerianos e Hamiltonianos. Grafos sem circuitos. Redes. Fluxos em redes.

Objetivos: Introduzir conceitos básicos da Teoria dos Grafos. Apresentar problemas que podem ser representados por grafos. Apresentar algoritmos importantes para a solução de problemas mais conhecidos.

Formato do Curso: O Curso terá a duração de 30 horas (2 créditos), compreendendo 18 aulas, com 2h de duração.

Avaliação: A avaliação constará de um conjunto de mini-provas e um pequeno projeto. O projeto é obrigatório. O aluno pode faltar a 20% das mini-provas. A nota final é calculada a partir da média aritmética das notas das mini-provas (65%) e da nota do projeto (35%). O aluno pode olhar cada mini-prova e discutir a sua nota até uma semana após a data de sua publicação. As mini-provas serão surpresas, sem data marcada (pelo menos uma por semana). A data do exame final já está definida:

• Final: 11/12/2009

Programa: O detalhamento do programa é o seguinte:

1. Introdução à Teoria dos Grafos

Motivação. Exemplos de aplicação.

2. Conceitos Básicos

Definição e notação. Subgrafos. Grafos completos e bipartidos. Isomorfismo de grafos. Complemento de um grafo. Grafos rotulados e grafos planares. Cliques. Conjunto Independente de Vértices. Cobertura de Vértices.

3. Representação de Grafos

Matriz de adjacências. Listas.

4. Caminhos e Circuitos

Caminhos, percursos, trajetos e ciclos de grafos. Caminhos e ciclos Hamiltonianos e Eulerianos. Grafos conexos e desconexos. Distância entre vértices. Exclusão e inclusão de arestas.

5. Digrafos

Dígrafos fortemente conexos e fracamente conexos. Alcançabilidade de vértices. Dígrafo acíclico. Aplicações.

6. Grafos Valorados

Grafos valorados. Menor caminho. Algoritmo de Djikstra.

7. Conectividade, Planaridade e Coloração

Conectividade: cortes, grafos k-conexos. Planaridade: grafos planares, fórmula de Euler. Coloração: grafos k-coloríveis, o problema das 4 cores.

8. Árvores

Árvore e floresta. Árvore geradora. Raiz de uma árvore, nível de um vértice, árvores m-ária. Árvores geradoras de custo mínimo. Algoritmos de Prim e Kruskal.

9. Busca em Grafos

Algoritmo básico. Busca em profundidade e amplitude.

10. Fluxos em Redes

Fluxos em redes. Cortes. Teorema do fluxo máximo.

Bibliografia:

• Szwarcfiter, J. L.
  Grafos e Algoritmos Computacionais. Editora Campus, 1986.
• Boaventura Netto, P. O.
  Grafos: Teoria, Modelos, Algoritmos. Edgar Blücher, 1996.
• Gersting, J. L.
  Fundamentos Matemáticos para a Ciência da Computação. LTC, 1995.
• Goodaire, E. G. e Parmenter, M. M.
  Discrete Mathematics with Graph Theory. Prentice-Hall, 1997.
• Diestel, Reinhard

Graph Theory. Springer-Verlag, 2000. (cópia eletrônica)

Planejamento de Aulas:

Aula	Data	Assunto Planejado
1	11/08/09	- Apresentação do Curso. Motivação para o estudo da teoria dos grafos. Introdução informal
2	14/08/09	- Definição e conceitos básicos: grau de vértices, multigrafos, grafos bipartidos, grafos completos, isomorfismo, complemento de grafos. - Representação de Grafos: Lista de Adjacência, matriz de Adjacência e Matriz de Incidência.
3	18/08/09	- Caminho, Trilha, Circuito, Ciclo. Grafos Conectados. - Grafos Dirigidos e Torneios.
4	21/08/09	- Busca em Grafos: DFS e BFS.
5	01/09/09	Aula de revisão
6	04/09/09	- Componentes Fortemente Conectados. - Ordenação Topológica
7	08/09/09	- Cliques, Cobertura de Vértices e Conjunto Independente de Vértices.
8	11/09/09	- Menor Caminho com Origem Única. - Algoritmo de Dijkstra. - Algoritmo de Bellman-Ford.
9	15/09/09	- Algoritmo de Floyd-Warshall. - Fechamento transitivo
10	18/09/09	Aula de revisão
11	22/09/09	- Árvores: Conceitos básicos.
12	25/09/09	- Árvore Binária. Árvore binária de Pesquisa. Heap Binário.
13	29/09/09	- Árvore de cobertura mínima. Algoritmos de Kruskal. - Algoritmo de Prim.
14	02/10/09	- Planaridade em Grafos: Conceitos básicos. Fórmula de Euler. Homeomorfismo. - Coloração em Grafos: Conceitos básicos. Teorema das 4 cores.
15	06/10/09	- Fluxo em Redes: conceitos básicos. - O Método de Ford-Fulkerson. - Teorema do Fluxo Máximo/Corte Mínimo.
16	09/10/09	- Emparelhamento: conceitos básicos. Emparelhamento em grafos bipartidos.
17	08/12/09	Aula de revisão
18	11/12/09	Prova Final