Teoria dos Grafos
| Departamento | Unidade | |||
|---|---|---|---|---|
| Ciência da Computação | CAC - Campus de Catalão | |||
| Nome da Disciplina | Código | Período | ||
| Teoria dos Grafos | 170 | 6 | ||
| Carga Horária Semestral | Carga horária Semanal | Ano | Semestre | |
| 64h | Teórica: 4h | Práticas: 0h | 2013 | 02 |
Noções básicas de grafos: motivos para estudar a teoria dos grafos; definição de grafos; definição de caminhos, trajetos e ciclos; graus de vértices e contagem; grafos dirigidos. Clique. Subgrafo.
Representação de grafos: Matriz de abjacências. Listas.
Distâncias: ditâncias de vértices e limitantes superiores; estrutura de grafos k-cromáticos.
Coloração: Coloração de vértices e limitantes superiores; estrutura de grafos k-cromáticos
Matching: Matchings e coberturas; algoritmos e aplicações; matchings em grafos gerais.
Conjuntos independentes de vértices.
Planaridade: grafos planares; formula de Euler.
Problemas de caminho mínimo: Árvores geradoras de custo mínimo; Algoritmo de Prim e kruskal; algoritmo de dijkstra; Algoritmo de Boruvka;
Problemas eulerianos e hamiltonianos
Fluxo de redes
Noções básicas de grafos; Representação de grafos; Distâncias; Coloração; Matching; Conjuntos independentes de vértices; Planaridade; Problemas do caminho mínimo; Problemas Eulerianos e Hamiltonianos; Fluxo em redes.
- SZWARCFITER, J. L., Grafos e Algoritmos Computacionais, Editora Campus,1984.
- YELENN, J, Gross, J. Graph Theory and Its Applications. CRC Press, 1998
- WEST, D. Introduction to Graph Theory, Prentice Hall, 2000
- GIBBONS, Alan - Algorithmic Graph Theory,Cambridge University Press, 1994.