Introduç˜ao `a Teoria dos grafos

Introdução à Teoria dos grafos
Bacharelado em Ciência da Computação e em Matemática
(diurno)
1o semestre de 2009
Prof. Claus Akira Horodynski Matsushigue
Terças e quintas: 14h–16h
Xerox: pasta 101 do DCE
Este é o arquivo Grafo-09.1d-ProgBib.pdf, que está impresso na pasta do curso,
assim como também está disponı́vel na URL:
http://clausahm.mat.unb.br/area/Grafo-09.1d/
e no site oficial deste curso no Sistema Moodle:
http://aprender.unb.br/
Programa
Capı́tulo I – Noções básicas de grafo
§1 Definições básicas
§2 Clique, conjunto independente e corte
§3 Caminho e ciclo
§4 Grafo partido, cobertura e conectividade
§5 Árvore
Capı́tulo II – Tópicos em grafo
§1 Busca de vértices
∗
∗
∗
∗
Busca/percurso de vértices
Busca em largura
Busca em profundidade
Grafo de blocos e vértice de corte
§2 Árvore geradora e caminho mı́nimo
∗
∗
∗
∗
∗
Busca/percurso de arestas
Algoritmo de Prim para árvore geradora mı́nima
Algoritmo de Dijkstra para caminhos mı́nimos
Algoritmo de Kruskal para árvore geradora mı́nima
Algoritmo de Floyd–Warshall para caminhos mı́nimos
1
§3 Emparelhamento e grafo bipartido
∗ Algoritmo de Edmonds para emparelhamento em grafos bipartidos
§4 Fluxo
∗ Algoritmo de Ford–Fulkerson para fluxo máximo e corte mı́nimo
§5 Caminho euleriano e hamiltoniano (se der tempo!)
§6 Coloração de vértice e de aresta (se der tempo!)
§7 Planaridade (se der tempo!)
Bibliografia
• Jair Donadelli Jr., Algoritmos e Teoria dos Grafos.
http://www.inf.ufpr.br/jair/ci065/ (resumo) – texto no Moodle
• Reinhard Diestel, Graph Theory.
• John A. Bondy e U.S.R. Murty, Graph theory.
• Béla Bollobás, Morden graph theory.
• P. Feofiloff, Y. Kohayakawa, Y. Wakabayashi, Uma introdução sucinta à Teoria dos grafos.
http://ime.usp.br/∼pf/teoriadosgrafos
• Paulo Feofiloff, Exercı́cios em Teoria dos grafos.
http://ime.usp.br/∼pf/grafos-exercicios
• Robin J. Wilson, Introduction to graph theory. (◦)
• Frank Harary, Graph Theory. (◦)
• John A. Bondy e U.S.R. Murty, Graph theory with applications. (◦)
• Jayme L. Szwarcfiter, Grafos e Algoritmos Computacionais. (◦)
• Cláudio L. Lucchesi, Introdução à Teoria dos Grafos.
• Alan Gibbons, Algorithmic Graph Theory.
• Gary Chartrand e Linda Lesniak, Graphs e digraphs. (◦)
• Robert Sedgewick, Algorithms in C, Part 5: Graph Algorithms.
• Donald E. Knuth, The Stanford GraphBase: A platform for combinatorial computing.
(◦) Existem na biblioteca da UnB.
Atendimento
• Pelo Sistema Moodle
• Pessoalmente nas terças-feiras, 16h15
Provas
• Primeira prova: 12 de maio (terça-feira), 14h
• Segunda prova: 09 de julho (quinta-feira), 14h
Pesos: respectivamente 1 e 2.
2