Aula 4

Aula 4

1. Grafos Eurelianos

   • Revisão de conceitos
     • Grafo: caminho (cadeia) não orientado ( sem seta)
       • Grafo direcionado ( dígrafo ) com setas mesma orientação
         • Circuito ou ciclo: começa e termina no mesmo vértice
           • Simples: se não passar mais de uma vez pela aresta
           • Conectividade
             • Grafos não orientado: conexo porque existe um caminho entre cada par de vértice
             • Grafo desconexo: falta uma possibilidade de caminho
             • Componente conexa: sub-grafo, encontrar sub-grupos
   • Pontes de Euler
     • Abstração por um grafo
       • Passar por um grafo sem repetir
     • Grafo pode possuir um percurso euleriano mas não ser um grafo euleriano
       • Grafo Euleriano é sair de um ponto e voltar pra ele mesmo
   • Como encontra ciclo euleriano?
     • Algoritmo de Hierholzer
       • Começa em qualquer vértice até voltar ao mesmo ponto
         • Fazendo vários ciclos
           • Depois juntar todos os ciclos
   • Problema carteiro Chinês
     • Eulerização do grafo: acrescentar mínimo de arestas