A tabela as seguir apresenta todas as disciplinas com vagas disponíveis para os discentes do Curso de ENGENHARIA COMPUTACIONAL (65B) da Universidade Federal de Juiz de Fora (UFJF) no período letivo atual. Os horários e os docentes responsáveis por cada disciplina podem ser consultados clicando na turma desejada.
Ressalta-se que o Curso de Engenharia Computacional da UFJF é ofertado em período integral, com aulas de segunda a sexta-feira, podendo ocorrer nos turnos matutino (8h às 12h), vespertino (14h às 18h) ou noturno (19h às 23h), conforme estabelecido na grade curricular.
Plano de Ensino
Disciplina: DCC059 - TEORIA DOS GRAFOS
Horas Aula: 4
Departamento: DEPTO DE CIENCIA DA COMPUTACAO /ICE
Ementa
1. Iniciação a Teoria dos Grafos
2. Grafos sem circuitos, árvores e arborescências
3. Busca em Grafos
2. Grafos sem circuitos, árvores e arborescências
3. Busca em Grafos
Conteúdo
1 - INTRODUÇÃO A MODELOS EM GRAFOS
- Grafos e Digrafos;
- Famílias comuns de Grafos;
- Modelagem de aplicações usando Grafos;
- Passeios e distâncias;
- Caminhos, ciclos e árvores;
- Grafos rotulados nos vértices e nas arestas;
- Árvores: caracterização e propriedades.
2 - ESTRUTURA E REPRESENTAÇÃO DE GRAFOS
- Grafos isomorfos;
- Subgrafos;
- Operações comuns entre grafos;
- Testes para grafos não-isomorfos;
- Representação de grafos por matriz;
- Representação de grafos por listas de adjacência.
3 - ÁRVORES GERADORAS CAMINHOS MÍNIMOS
- Árvore de crescimento;
- Busca em largura;
- Busca em profundidade;
- Identificando componentes conexas;
- Identificando arestas ponte e nós de articulação;
- Algoritmos Gulosos
- Árvore de cobertura mínima;
Algoritmo de Prim;
Algoritmo de Kruskal;
- Algoritmos de Dijkstra e Floyd para caminho mínimo
- Corte mínimo de arestas;
4 - CONECTIVIDADE E CAMINHAMENTO EM GRAFOS
- k-conectividade de vértice;
- k-conectividade de arestas;
- Relação entre conectividades de vértice e aresta;
- Trilhas e ciclos Eulerianos;
- Caminhos e ciclos Hamiltonianos;
5 - PLANARIDADE EM GRAFOS
- Conceito de desenho planar de um grafo;
- Teorema da curva de Jordan;
- Teorema de Kuratowski;
6 - PROBLEMAS CLÁSSICOS MODELADOS EM GRAFOS
- Problema da clique;
- Problema do subconjunto independente;
- Problema do subconjunto dominante;
- Problema de Cobertura de vértices;
- Problemas de coloração;
- Problema de atribuição;
- Problema da árvore de Steiner;
- Problema do Caixeiro Viajante;
- Grafos e Digrafos;
- Famílias comuns de Grafos;
- Modelagem de aplicações usando Grafos;
- Passeios e distâncias;
- Caminhos, ciclos e árvores;
- Grafos rotulados nos vértices e nas arestas;
- Árvores: caracterização e propriedades.
2 - ESTRUTURA E REPRESENTAÇÃO DE GRAFOS
- Grafos isomorfos;
- Subgrafos;
- Operações comuns entre grafos;
- Testes para grafos não-isomorfos;
- Representação de grafos por matriz;
- Representação de grafos por listas de adjacência.
3 - ÁRVORES GERADORAS CAMINHOS MÍNIMOS
- Árvore de crescimento;
- Busca em largura;
- Busca em profundidade;
- Identificando componentes conexas;
- Identificando arestas ponte e nós de articulação;
- Algoritmos Gulosos
- Árvore de cobertura mínima;
Algoritmo de Prim;
Algoritmo de Kruskal;
- Algoritmos de Dijkstra e Floyd para caminho mínimo
- Corte mínimo de arestas;
4 - CONECTIVIDADE E CAMINHAMENTO EM GRAFOS
- k-conectividade de vértice;
- k-conectividade de arestas;
- Relação entre conectividades de vértice e aresta;
- Trilhas e ciclos Eulerianos;
- Caminhos e ciclos Hamiltonianos;
5 - PLANARIDADE EM GRAFOS
- Conceito de desenho planar de um grafo;
- Teorema da curva de Jordan;
- Teorema de Kuratowski;
6 - PROBLEMAS CLÁSSICOS MODELADOS EM GRAFOS
- Problema da clique;
- Problema do subconjunto independente;
- Problema do subconjunto dominante;
- Problema de Cobertura de vértices;
- Problemas de coloração;
- Problema de atribuição;
- Problema da árvore de Steiner;
- Problema do Caixeiro Viajante;
Bibliografia
SZWARCFITER, J. Grafos e Algoritmos Computacionais. Editora Campus, 1983.
BOAVENTURA NETTO, P. O. Grafos: Teoria, Modelos e Algoritmos. Editora Edgard Blucher Ltda, 1996.
CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; STEIN, C. Introduction to Algorithms. 2nd. edition. MIT Press, 2001.
BOAVENTURA NETTO, P. O. Grafos: Teoria, Modelos e Algoritmos. Editora Edgard Blucher Ltda, 1996.
CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; STEIN, C. Introduction to Algorithms. 2nd. edition. MIT Press, 2001.
Bibliografia(continuação)
Não informado
Bibliografia complementar
BOAVENTURA NETTO, P. Grafos - Teoria, Modelos e Algoritmos. 4ª ed. 2006.
BOAVENTURA NETTO, P. Grafos - Introdução e Prática. Blucher, 2009.
CORMEN, T.; LEISERSON, C.; RIVERST, R.; STEIN, C. Algoritmos - Teoria e Prática. Campus, 2002.
BOAVENTURA NETTO, P. Grafos - Introdução e Prática. Blucher, 2009.
CORMEN, T.; LEISERSON, C.; RIVERST, R.; STEIN, C. Algoritmos - Teoria e Prática. Campus, 2002.