Tópicos e conceitos de Teoria dos Grafos
Segue uma lista de tópicos, conceitos e resultados importantes.
Vários deles você já conhece;
outros você precisa aprender.
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!
-
indução matemática
-
caminhos e circuitos
-
subgrafos
-
tipos de grafos: caminhos, circuitos, grades, cubos,
bipartidos,
florestas, árvores,
planares,
…
-
cortes
-
grafos conexos e componentes
-
florestas e árvores
-
pontes e grafos aresta-biconexos
-
articulações e grafos biconexos
-
grafos planares e mapas planos
-
isomorfismo
-
grafos bipartidos
-
conjuntos estáveis e cliques
-
cobertura por vértices
-
coloração de vértices e número cromático
-
emparelhamentos
-
problema do emparelhamentos máximo
-
teorema de König (emparelhamentos em grafos bipartidos)
-
dualidade emparelhamentos/coberturas em grafos bipartidos
-
teorema de Hall (emparelhamentos em grafos bipartidos)
-
coloração de arestas e índice cromático
-
circuitos e caminhos hamiltonianos
-
decomposição em circuitos
-
ciclos eulerianos
-
conectores mínimos e conjuntos acíclicos máximos
-
subflorestas máximas
-
caminhos e circuitos mínimos
-
coleções disjuntas de caminhos
-
conexidade
-
teoremas de Menger
-
menores (= minors)
e menores topológicos
-
teorema de Kuratowski
-
teorema de Wagner