Grafos

Grafos

1. Abstrair e codificar

   • Pares de objetos

2. Conjunto de pontos

   • Formado por:
     • Aresta
       • Par adjacente de vértice
     • Vértice
       • Grau de um vértice

3. Para que serve?

   • Solução de problemas
     • GPS (Caminho mínimo)
     • Fluxo de rede
     • Alocação de recursos

4. Tipos

   • Digrafo
     • Arestas possuem direções
   • Planar
     • Não há interseção entre as arestas
   • Árvore
     • Grafo conexo sem circuito
       • Um grafo é dito conexo se existir um caminho entre dois vertices
   • Isomorfo
     • Não muda
       • Diferentes representações
       • Mesmo grafo

5. Possui

   • Ciclos
     • Eulariano
       • Percorre as arestas do grafo uma única vez
     • Hamiltoniano
       • Percorre os vértices do grafo uma única vez