Teoria dos Grafos

 

Jorge César Abrantes de Figueiredo

 

Período: 2006.1

 

Quadro de Avisos:

Veja sua nota aqui.

 

 

 

Horário: S121 e I071

Sala: Reenge 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 32 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 parciais. 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:

 

 

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:

 

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

 

 

 

 

Planejamento de Aulas:

 

Aula

Data

Assunto Planejado

Notas de Aula

1

13/07/06

Apresentação do Curso. Motivação para o estudo da teoria dos grafos. Introdução informal

Apresentação

 

2

17/07/06

Definição e conceitos básicos: grau de vértices, multigrafos, grafos bipartidos, grafos completos, isomorfismo, complemento de grafos.

conceitosBásicos

Lista 1

3

20/07/06

Representação de Grafos: Lista de Adjacência, matriz de Adjacência e Matriz de Incidência.

Representação

4

24/07/06

Cliques, Cobertura de Vértices e Conjunto Independente de Vértices.

cliques

5

27/07/06

Caminho, Trilha, Circuito, Ciclo. Grafos Conectados.

conectividade

Lista 2

6

31/07/06

Grafos Dirigidos e Torneios.

Digrafos

7

03/08/06

Aula de exercício

 

8

07/08/06

Busca em Grafos: DFS e BFS.

Busca

9

10/08/06

Componentes Fortemente Conectados.

Ordenação Topológica

Componentes

Lista 3

10

14/08/06

Aula de revisão

 

11

17/08/06

Prova 1

 

12

21/08/06

Menor Caminho com Origem Única. Algoritmo de Dijkstra.

Menor Caminho

13

24/08/06

Algoritmo de Bellman-Ford. Algoritmo de Floyd-Warshall.

 

14

28/08/06

Aula de Exercícios

 

15

31/08/06

Árvores: Conceitos básicos.

Árvores

16

04/09/06

Árvore Binária. Árvore binária de Pesquisa. Heap Binário.

Cobertura Mínima

17

11/09/06

Árvore de cobertura mínima. Algoritmos de Kruskal e Prim.

Lista 4

18

14/09/06

Mais aplicações de árvores.

 

19

18/09/06

Aula de revisão

 

20

21/09/06

 

 

21

25/09/06

Prova 2

 

22

28/09/06

Planaridade em Grafos: Conceitos básicos. Fórmula de Euler. Homeomorfismo.

planaridade

23

02/10/06

Coloração em Grafos: Conceitos básicos. Teorema das 4 cores.

coloracao

24

05/10/06

 

 

25

09/10/06

Fluxo em Redes: conceitos básicos.

Fluxo em Rede

26

12/10/06

O Método de Ford-Fulkerson. Teorma do Fluxo Máximo/Corte Mínimo.

 

27

16/10/06

Emparelhamento: conceitos básicos. Emparelhamento em grafos bipartidos.

Emparelhamento

28

19/10/06

Emparelhamento: aplicacoes.

Lista 5

29

23/10/06

Aula de Revisão

 

30

26/10/06

 

 

31

30/10/06

Prova 3

 

32

06/11/06

Repo 3

 

33

09/11/06

Prova Final