Teoria dos Grafos
DCE144 - 2008/2
| Bibliografia | Plano de Curso | Aulas | Provas | TP1 | TP2 | TP3 | TP4 | TP5 | Seminário | Notas |
- Grafos - Teoria, Modelos e Algoritmos
Autor:Paulo O. Boaventura Netto. 4ª edição.Editora Edgard Blücher. 2006.Bibliografia Complementar:
Algoritmos
Autores: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Tradução da 2ª edição americana. Editora Campus. 2002.Leitura Complementar (material digital):
Horário e Sala:
------------------------------------------------------
Segunda Terça Quarta Quinta Sexta
------------------------------------------------------
13:00 S-105
14:00 S-105
15:00
16:00
17:00
------------------------------------------------------
19:00 S-205
20:00 S-205
21:00
22:00
23:00
------------------------------------------------------
Programação e Download de Aulas:
Dia Tópicos e Aulas Aulas
Leitura adicional*
05/08/2008
Um pouco de história download 08/08/2008
Introdução - Conceitos básicos download 19/08/2008
Introdução - Representação computacional download 22/08/2008
Busca em Profundidade (DFS) download 26/08/2008
Explicação geral dos trabalhos práticos (código base) - 29/08/2008
Conexidade e Conectividade em Grafos download 09/09/2008
Aula de apresentação de TP1 e TP Extra - 12/09/2008
Busca em Largura (BFS) download 16/09/2008
Propriedades da BFS e da DFS download 18/09/2008
Aula tira dúvidas (reposição) - 19/09/2008
Prova 01 - 23/09/2008
Árvore Geradora Mínima - Algoritmo Genérico download 26/09/2008
Árvore Geradora Mínima - Algoritmo de Kruskal download 30/09/2008
Árvore Geradora Mínima - Algoritmo de Prim download 03/10/2008
Caminhos Mais Curtos de origem única download " Algoritmo de Bellman-Ford " 07/10/2008 Ordenação Topológica download " Caminhos Mais Curtos de origem única em grafos acíclicos " 10/10/2008 Apresentação do TP2 - Sala D-303 - 14/10/2008 Recesso Acadêmico - 17/10/2008 Recesso Acadêmico - 21/10/2008 Algoritmo de Dijkistra download 24/10/2008 Prova 02 - 28/10/2008 Apresentação do TP3 - Sala D-303 - 31/10/2008 Fluxo Máximo download 04/11/2008 Algoritmo de Ford-Fulkerson download 07/11/2008 O Problema do Emparelhamento Bipartido Máximo download 11/11/2008 Seminários 14/11/2008 Seminários 18/11/2008 Seminários 21/11/2008 Afastamento - 25/11/2008 Prova 03 - 28/11/2008 Apresentação do TP4 - 02/12/2008 Prova especial - 12/12/2008 Prova final - Horário: 13h. Sala: S-105 - * A Leitura adicional é opcional.
** Atenção: A matéria da última prova é referente a matéria de todo o semestre.O conteúdo cobrado na prova final será de toda a matéria dada no semestre;
O conteúdo cobrado na prova especial será de toda a matéria dada no semestre;
- Prova 1:
- Representação, Busca em Largura, Busca em Profundidade, Conexidade;
- Prova 2:
- AGM, Prim, Kruskal, Caminhos mais curtos (algoritmos relacionados) + matéria da prova 1;
- Prova 3:
- Toda a matéria dada;
- Prova Especial:
- 02/12/2008;
Toda a matéria dada;- Prova Final:
- 12/12/2008 - S-205;
Toda a matéria dada;- Download das provas:
- Implementação de Algoritmos em grafos;
- Documentação; //atenção - documentação em segunda versão - corrigida
- Código base; //atenção - código em segunda versão - corrigida
- Exemplo de grafo que deve ser carregado:
- Implementar:
- Representação utilizando;
- Matriz de Adjacência;
- Matriz de Incidência;
- Lista de Adjacência;
- Algoritmos;
- carregarGrafo
- existeCiclo;
- arestasDeArvore;
- arestasDeRetorno;
- arestasDeAvanco;
- arestasDeCruzamento;
- componentesFortementeConectados;
- ordenacaoTopologica;
- agmUsandoPrim;
- agmUsandoKruskall;
- custoDaArvoreGeradora;
- ehArvoreGeradora;
- caminhoMaisCurto;
- custoDoCaminho;
- ehCaminho.
Entrega: 09/09/2008: 3 Representações + carregarGrafo + existeCiclo;
A interface deve permitir a escolha da representação utilizada antes de carregar o grafo da memória secundária.
Também deve possuir um campo para a indicação do caminho do arquivo que deve ser carregado;
Valor: 5 pontos
Data de entrega: 10/10/2008
Valor: 5 pontos;
Funções que devem ser implementadas:
- componentesFortementeConectados;
- arestasDeArvore;
- arestasDeRetorno;
- arestasDeAvanco;
- arestasDeCruzamento;
- Exemplo de grafo que deve ser carregado:
Arquivos de teste:
Data de entrega: 24/10/2008
Valor: 5 pontos;
Funções que devem ser implementadas:
- agmUsandoKruskall;
- gmUsandoPrim;
- custoDaArvoreGeradora;
- ehArvoreGeradora;
Vou disponibilizar os arquivos para teste no dia da aula de apresentação.
- Exemplo de grafo que deve ser carregado:
- Fluxo Máximo de Custo Mínimo:
- Estratégia gulosa sugerida:
- Durante a execução do Algoritmo de Ford-Fulkerson, quando o algoritmo procura um caminho aumentante, uma idéia é escolher o caminho aumentante de custo mínimo;
- Obviamente que esta estratégia só funciona se não existe ciclo de custo negativo no grafo.
- O algoritmo sugerido é ótimo (ou seja, o resultado de todos os alunos deve ser o mesmo).
- Exemplo de grafo que deve ser carregado:
- Imagem;
- Arquivo txt correspondente; //grafo orientado ponderado indicando a capacidade;
- Arquivo txt correspondente; //grafo orientado ponderado indicando o custo; Este vocês já implementaram... O peso já implementado servirá de custo no fluxo máximo.
- Valor: 10 pontos.
- Data de entrega: 28/11/2008. //não vou aceitar entregas com atraso;
- Ao final da execução, duas informações precisam ser mostradas:
- A quantidade de fluxo enviada da origem para o destino;
- O custo de enviar aquele fluxo pela rede;
- Adaptações na base disponibilizada anteriormente:
- Classe Aresta com a variável adicional de capacidade e métodos de encapsulamento; download;
- Classe Grafo que permite setar a capacidade de uma aresta; download;
- Classe AlgoritmosEmGrafos com função fluxoMaximoDeCustoMinimo e função para carregar grafos com as capacidades das arestas; download;
- Nova classe chamada RetornoFluxoMaximoDeCustoMinimo. Representa o retorno da função de fluxo máximo de custo mínimo; download;
- Instâncias de teste:
- 11/11/2008:
- Theodoro e Danilo Braga;
- Edgar e Flávio;
- Neubio e José Alexandre;
- 14/11/2008:
- Geraldo Lucas e Danilo;
- Juliana e Itael;
- Tiago e Robson;
- 18/11/2008:
- Max e Lucas;
- Luis Henrique e Alexsander;
- Tatiane, Filipe e Adriano;
Aluno(a) Prova 1 Prova 2 Prova 3 TP1 TP2 TP3 TP4 TP
ExtraBon. Sem. Total 1 06.2.08.035 8,0 0,0 0,0 0,0 0,0 0,0 0,0 0,0 3,0 4,0 15,0 2 07.2.08.042 11,0 21,0 13,0 0,0 5,0 2,5 2,0 10,0 3,0 4,0 71,5 3 06.2.08.019 14,0 15,0 12,0 0,0 0,0 0,0 3,0 8,0 3,0 4,0 59,0 4 06.2.08.003 15,0 20,0 17,0 5,0 5,0 5,0 0,0 8,0 3,0 4,0 82,0 5 06.2.08.004 12,0 11,5 0,0 0,0 0,0 0,0 0,0 8,0 3,0 5,0 39,5 6 06.2.08.005 18,0 21,0 18,5 5,0 5,0 5,0 0,0 8,0 3,0 4,0 87,5 7 06.2.08.007 13,0 24,0 19,5 3,0 5,0 5,0 0,0 8,0 3,0 4,0 84,5 8 06.2.08.008 13,0 7,5 17,0 0,0 5,0 5,0 0,0 9,0 3,0 4,0 63,5 9 06.2.08.009 6,0 10,5 13,0 0,0 0,0 3,5 0,0 8,0 3,0 5,0 49,0 10 06.2.08.013 14,0 18,0 21,0 5,0 5,0 5,0 0,0 8,0 3,0 5,0 84,0 11 06.2.08.014 14,0 21,0 14,0 5,0 5,0 5,0 0,0 8,0 3,0 4,0 79,0 12 06.2.08.018 14,0 12,0 12,0 0,0 0,0 0,0 10,0 8,0 3,0 5,0 64,0 13 06.2.08.020 11,0 14,0 22,0 5,0 5,0 5,0 5,0 0,0 3,0 4,0 74,0 14 06.2.08.021 6,0 7,0 5,5 0,0 0,0 0,0 0,0 8,0 3,0 4,0 33,5 15 06.2.08.024 8,0 14,5 22,0 5,0 5,0 5,0 0,0 10,0 3,0 5,0 77,5 16 06.2.08.025 10,0 9,5 12,0 3,0 2,5 4,0 2,0 0,0 3,0 5,0 51,0 17 06.2.08.031 6,0 12,5 19,5 0,0 0,0 4,5 2,0 8,0 3,0 5,0 60,5 18 06.2;08.036 6,0 15,0 11,5 0,0 0,0 0,0 0,0 0,0 3,0 4,0 39,5 19 06.2.08.040 14,0 26,5 23,5 2,0 5,0 6,0 10,0 8,0 3,0 5,0 103,0 Desvio 3,6 6,6 6,9 2,3 2,5 2,3 2,5 3,5 0,0 0,5 22,2 Média 11,2 14,8 14,4 2,0 2,8 3,2 1,3 6,6 3,0 4,4 63,6 Total -- 20,0 27,5 27,5 5,0 5,0 5,0 10,0 10,00 3,0 5,00 118,0
