Repositório pessoal pra material de Teoria dos Grafos. Se alguém achou isso por acaso, espero que te ajude :)
(nada por enquanto)
Listas da matéria de matemática discreta ministrada por Maria Soledad.
Lista 8: (Enunciado) (Respostas)
Lista 9: (Enunciado) (Respostas)
Materiais diversos como pdfs, livros, slides e imagens.
As listas e materiais são baseados no livro de Richard Johnsonbaugh.
- Introdução: Definição, Exemplos e Problemas de Grafos
- Conceitos Gerais: Vizinhança, Ordem, Grau, Laço, Caminhos, Ponto isolado, Subgrafo, Subconjuntos de um Grafo e Componentes de um Grafo
- Tipos de Grafo: Grafo-Dirigido, Grafo Subjacente, Multi-Grafo, Grafo Trivial (e Teoremas de Grafos), Grafo Completo, Grafo Bipartido e Grafo com Peso
- Ciclo Euleriano
- Ciclo Hamiltoniano
- Algoritmo Djikstra
- Matriz de Adjacências e Matriz de Incidências
- Isomorfismo e Homeomorfismo de Grafos (+ Teorema de Kuratowski)
- Grafos Planares e Fórmula/Propriedade de Euler
- Arestas em Série e Redução em Série
- Coloração (Grafos, Vértices e Arestas)
- K-Colorível (+ Teorema das 4 cores, Teorema grafo 6-colorivel, 5-colorivel, 4-colorivel, etc.)
- Número Cromático (+ Teorema de Vizing, etc.)
- Árvores (Definição, Altura, Nível, Propriedades, Afirmações e Aplicações)
- Árvores Geradoras
- Algoritmo Bfs (Breadth-first search: busca em largura por árvore geradora)
- Algoritmo Prim (retorna conjunto de arestas da árvore geradora minimal) e Árvores Geradoras Minimais
- Redes e Fluxo
- Fluxo Maximal
- Algoritmo Maxflow (retorna fluxo maximal)
- Corte: definição, capacidade de corte, teorema da capacidade e Teorema do Corte Mínimo/Fluxo Maximal e Teorema do Maxflow
- Matching