Caminho hamiltoniano: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 9:
==Definições==
[[Ficheiro:Mycielski graph k4 hamiltonian path.svg|thumb|Um caminho hamiltoniano no grafo de Mycielski.]]▼
[[Imagem:Hamilton path.gif|right|frame|Um caminho Hamiltoniano (em preto) sobre um grafo (em azul).]]
Linha 27 ⟶ 26:
*Todo [[sólido platônico]], considerado como um grafo é Hamiltoniano
==Propriedades==
▲[[Ficheiro:Mycielski graph k4 hamiltonian path.svg|thumb|Um caminho hamiltoniano no grafo de Mycielski.]]
Qualquer ciclo hamiltoniano pode ser convertido para um caminho Hamiltoniano, removendo-se uma de suas arestas, mas um caminho Hamiltoniano só pode ser estendido para um ciclo hamiltoniano se suas extremidades são adjacentes.
O [[grafo linha]] de um grafo Hamiltoniano é Hamiltoniano. O grafo linha de um [[grafo Euleriano]] é Hamiltoniano.
Um torneio (com mais de 2 vértices) é Hamiltoniano se e seomente se ele é [[|Componente fortemente conectado|fortemente conectado]].
Um ciclo Hamiltoniano pode ser usado como base de uma [[prova com zero conhecimentos]].
Número de diferentes ciclos hamiltonianos para um grafo completo = (n-1)! / 2.
Número de diferentes ciclos hamiltonianos para um grafo orientado completo = (n-1)!.
{{Referências}}
| |||