Weby shortcut 1a5a9004da81162f034eff2fc7a06c396dfddb022021fd13958735cc25a4882f

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
Conteúdo:

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

Ementa:

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.

Bibliografia:
  • 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.
Listar Todas Voltar