Please enable JavaScript.
Coggle requires JavaScript to display documents.
Grafos Hamiltonianos (Caminho Hamiltoniano (Caminho simples e aberto,…
Grafos Hamiltonianos
Caminho Hamiltoniano
Caminho simples e aberto
Passa por cada vértice uma vez
O comprimento é a quantidade de vértices menos 1
Grafo
NÃO
é hamiltoniano
Possui
somente
um caminho hamiltoniano
Se possui um caminho (aberto ou fechado) que inclui todos os vértices apenas uma vez
Não possui ciclo hamiltoniano
Remoção de
K
vértices resulta em um grafo desconectado de
K+1
componentes
Não possui ciclo e nem caminho hamiltoniano
Remoção de
K
vértices resulta em um grafo desconectado com
mais
do que
K+1
componentes
Grafo
É
hamiltoniano
Se possui um ciclo que inclui todos os vértices apenas uma vez
Grafos que contém um ciclo hamiltoniano
Simples
Conexo
Completo
n > 2 vértices
Condição
suficiente
mas não necessária
Um grafo de ordem
P
tal que grau de qualquer vértice seja >=
P/2
Ciclo Hamiltoniano
Atributos
Passa por cada vértice uma vez
Vértice inicial = vértice terminal
Caminho simples e fechado
Em um grafo
completo
Arestas
disjuntas
N (nº arestas) for
par
(N-2)/2
ciclos
N (nº de arestas) for
ímpar
e
>2
(N-1)/2
ciclos
Sem considerar arestas
disjuntas
(N-1)!/2
ciclos