MAC0328: Tópicos e palavras-chave
Para complementar o programa oficial,
segue uma lista de tópicos, conceitos e palavras-chave
relevantes para MAC0328.
Não espere que o professor apresente cada um desses tópicos!
Tome a iniciativa de perguntar ao professor
ou de aprender por conta própria!
-
digrafos (vértices e arcos)
-
digrafos simétricos
-
grafos (vértices e arestas)
-
estruturas de dados para digrafos e para grafos
-
tipos de digrafos: caminhos (dirigidos), circuitos (dirigidos),
digrafos acíclicos (DAGs)
-
tipos de grafos: caminhos, circuitos, grades, cubos,
bipartidos,
florestas, árvores,
planares
-
subgrafos e subdigrafos
-
grafos conexos e componentes
-
acessibilidade em digrafos
-
recursão e algoritmos recursivos
-
busca em profundidade (DFS)
-
busca em largura (BFS)
-
caminhos de comprimento mínimo
-
ordenação topológica de digrafos
-
componentes fortes de digrafos
e o algoritmo de Kosaraju-Sharir
-
cortes
-
árvores e florestas
-
árvores geradoras de grafos
-
árvores geradoras de peso mínimo de grafos (MST)
-
algoritmo de Prim para MST
-
algoritmo de Kruskal para MST
-
caminhos de peso mínimo em grafos
-
algoritmo de Dijkstra para caminhos de peso mínimo
-
articulações e grafos biconexos
-
grafos planares e mapas planos
-
grafos bipartidos
-
conjuntos estáveis e cliques
-
coloração de vértices e número cromático
-
emparelhamento máximo
-
emparelhamentos em grafos bipartidos (teoremas de König e Hall)
-
dualidade emparelhamentos/coberturas em grafos bipartidos
-
coloração de arestas e índice cromático
-
circuitos e caminhos hamiltonianos
-
ciclos eulerianos
-
coleções disjuntas de caminhos
-
fluxo máximo e o algoritmo de Ford e Fulkerson
