Teoria dos Grafos

Jorge César Abrantes de Figueiredo

Período: 2003.2

Veja a sua situação de faltas aqui.
Veja o plano de aulas aqui.
Veja o quadro de notas aqui.

A DATA DA PROVA FINAL É 22/04/2004.

Horário: S121 e I071

Sala: RE-08

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 34 aulas, com 1h de duração.

Avaliação: A avaliação constará de 3 exames parciais. A nota final corresponde a média aritmética das 3 notas. Todo aluno tem direito a fazer apenas uma reposição.Não existe a figura de reposição da menor nota. O aluno pode olhar a prova e discutir a sua nota até 10 dias após a sua publicação. As datas dos exames de avaliação já estão definidas:

Prova 1: 18/12/2003
Prova 2: 08/03/2004
Prova 3: 12/04/2004
Reposição 1: 22/12/2003
Reposição 2 e 3: 15/04/2004
Final: 22/04/2004

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.

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. Emparelhamento

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.
Wilson, R. J.

Introduction to Graph Theory. Prentice-Hall, 1996.

Planejamento de Aulas:

Aula	Data	Assunto	Observação
1	17/11/2003	Apresentação do Curso Motivação para o estudo da teoria dos grafos Introdução informal	Texto introdutório (ps, pdf) Slides da aula
2	20/11/2003	Definição e conceitos básicos grau de vértices multigrafos grafos bipartidos grafos completos isomorfismo complemento de grafos	Slides da Aula Conceitos Básicos (ps,pdf)
3	24/11/20	Representação de grafos: lista de adjacências matriz de adjacência matriz de incidência	Slides da Aula Representação de Grafos (ps, pdf) Lista de Exercícios (ps,pdf)
4	27/11/2003	Caminhos, percursos e trajetos Ciclo Euleriano e Hamiltoniano Primeiro teorema (grafo Euleriano)	Caminhos, percursos, etc. (ps,pdf)
5	01/12/2003	Aula de revisão
6	04/12/2003	Grafos conexos Digrafos Torneios	Slides da Aula Mini-Teste 1
7	11/12/2003	Busca em grafos: Busca em amplitude Busca em profundidade Ordenação topológica	Busca em Grafos
8	15/12/2003	Componentes fortemente conectados	Slides da Aula Lista de Exercícios 3 (ps,pdf)
9	18/12/2003	Prova 1
10	22/12/2003	Reposição 1
11	02/02/2004	Apresentação do programa da segunda parte do curso. Manor Caminho de origem única. Algoritmo de Dijkstra.	Menor Caminho
12	05/02/2004	Algoritmo de Bellman-Ford. Algoritmo de Floyd-Warshall.	Floyd-Warshall
13	09/02/2004	Árvores: Conceitos básicos, árvores enraizadas, árvores binárias.	Árvores
14	12/02/2004	Aplicação em ordenação: heap binário.
15	16/02/2004	Árvores binárias de pesquisa. Caminhamento.	Representação eABP (pdf, ps)
16	19/02/2004	Árvore de cobertura. Árvore de cobertura mínima.	Árvore de cobertura (pdf, ps)
17	26/02/2004	Algoritmo de Kruskal. Algoritmo de Prim.	Lista de exercício(pdf)
18	01/03/2004	Planaridade: conceitos básicos e Fórmula de Euler.
19	04/03/2004	Planaridade: grafos duais e grafos infinitos.	Planaridade
20	08/03/2004	Prova 2
21	11/03/2004	Coloração: número cromático e teoremas básicos.	Coloração (pdf, ps)
22	15/03/2004	Coloração: teorema das 4 cores.
23	29/03/2004	Fluxo em redes: conceitos básicos. Fluxos e cortes.	Fluxo em redes
24	01/04/2004	O método de Ford-Fullkerson.
25	05/04/2004	Aula de revisão.	Lista de Exercícios Prova Final - Período 03.1
26	12/04/2004	Prova 3
27	15/04/2004	Reposição das provas 2 e 3.
28	19/04/2004	Prova Final

Links: