MAC0320: Introdução à Teoria dos Grafos
Primeiro semestre de 2015
Diário
Tópicos cobertos nas aulas.
- Aula 1:
- Aula 2:
- Caminhos e ciclos
- Grafos bipartidos
- Aula 3:
- Aula 4:
- Raio, diâmetro,
cintura e circumferência
- Aula 5:
- Aula 6:
- Aula 7:
- Aula 8:
|
- Aula 9:
- Árvores
- Algoritmo de Kruskal
- Aula 10:
- Árvores
- Busca em largura e
profundidade
- Algoritmo de Dijkstra
- Aula 11:
- Emparelhamento
maximal e máximo
- Teorema de Berge
- Aula 12:
- Emparelhamentos
em grafos bipartidos
- Teorema de Hall
- Teorema de König-Egerváry
- Aula 13:
- Emparelhamentos
em grafos arbitrários
- Teorema de Tutte
- Aula 14:
- Cortes de vértices
- Teorema de Harary
- Aula 15:
- Cortes de arestas
- Teorema de Whitney
- Aula 16:
- Floresta/Árvore de blocos
- Grafos 2-conexos
|
- Aula 17:
- Caracterização dos grafos 2-conexos
- Decomposição em orelhas/orelhas fechadas
- Aula 18:
- Aula 19:
- Ciclos/Caminhos hamiltonianos
- Teorema de Dirac
- Teorema de Ore
- Teorema de Bondy-Chvátal
- Aula 20:
- Aula 21:
- Coloração de vértices
- Teorema de Brooks (Sem demostração)
- Grafos críticos
- Aula 22:
- Coloração de arestas
- Teorema de Vizing-Gupta
- Aula 23:
- Planaridade
- Teorema de Euler
- Aula 24:
- Planaridade
- Dualidade
- Teorema das cinco cores (Heawood)
|