Aula 5

Aula 5

1. Grafos hamiltonianos

   • Passar no vértice apenas uma vez
     • Se possui um caminho fechado (ciclo) é hamiltoniano
       • Ciclo hamiltoniano - passa-se por cada vértice exatamente uma vez
   • Se n= 2 contém um caminho hamiltoniano
     • Se n > 2 contém um ciclo hamiltoniano
   • Condições Suficientes
     • Condições Necessárias
   • Teoremas
   • Descobrir se um grafo não é hamiltoniano
     • Há no grafo G um vértice ou mais (k vértices), cuja remoção resulta em um grafo desconectado com k+1 componentes? Se houver, o grafo não é Hamiltoniano