O PCV é um dos mais tradicionais e conhecidos problemas de programação
matemática e lidam em sua maior parte com passeios ou tours sobre pontos de
demanda ou oferta. Dentre os tipos de passeios um dos mais importantes é o
denominado hamiltoniano. Seu nome é devido a Willian Rowan Hamilton que, em
Prove que sempre existe um circuito hamiltoniano em
um grafo conexo onde todos
os nós têm grau 2.
Base: Triangulo(facil)
Induçao:Suponha dado um grafo nesta condiçoes, com k
vertices,com um circuito hamiltoniano, pegue 2
vertices v1 e v2 arbitrarios
ligados por uma aresta e retire esta aresta
2 matches
Mail list logo