Teoria dos Grafos

---

• História
  • Problema das Sete Pontes de Königsberg
  • Teoria das Árvores
  • Problema das Quatro Cores
• Definições
  • Grafo
  • Função de incidência
  • Tipos de grafos
    • Grafos não direcionados
    • Grafos direcionados - Digrafo
  • Incidência e Adjacência
  • Arestas múltiplas ou arestas paralelas
  • Grafo simples
  • Grafo completo
  • Grau de vértices
    • Teorema de aperto de mãos
    • Grau de entrada de um vértice
    • Grau de saída em um vértice
  • Vizinhança de um vértice
  • Grafo regular
  • Complemento de um grafo
  • Grafos idênticos
  • Grafos isomorfos
• Representação de grafos
  • Matriz de adjacência
  • Lista de adjacência
• Subgrafos
  • Subgrafo gerador - Spanning subgraph
  • Subgrafo induzido
  • Subgrafo aresta-induzido
• Passeio em grafos
• Trilha em grafos
• Caminho em grafos
• Algoritmo de buscam em profundidade - DFS
• Provas
  • Prova da simetria de um dígrafo
  • Prova de grafo simples com vértices de grau 1, 1, 3, 3
• Ordenação topológica
  • Algoritmo de Kahn - Ordenação topológica
• Grafo bipartido
  • Prova de um grafo simples é bipartido
• Pontes ou Arestas de corte
  • Algoritmo ingênuo para detectar pontes em um grafo
  • Algoritmo otimizado para detectar pontes em um grafo
• Clique em Teoria dos Grafos