Introdução

Muitos dos problemas modelados em grafos admitem soluções computacionais e/ou matemáticas eficientes e elegantes. Um caminho hamiltoniano é um caminho que passa por todos os vértices de um grafo exatamente uma vez. Um ciclo hamiltoniano é um ciclo que passa por todos os vértices de um grafo exatamente uma vez. Um grafo é hamiltoniano se tem um ciclo hamiltoniano. O problema do ciclo hamiltoniano consiste em determinar se um grafo é hamiltoniano e foi provado ser NP-Completo.

Objetivos

Devido à dificuldade inerente a um problema NP-Completo, restringimos o estudo de ciclos hamiltonianos aos grafos ímpares O_k, com o objetivo de utilizar propriedades estruturais destes grafos para solucionar o problema.

Duas importantes conjecturas relativas à existência de ciclos hamiltonianos em O_k permanecem em aberto há décadas. Além da importância teórica, o problema tem inúmeras aplicações práticas em pesquisa operacional.

Devido ao alto número de vértices de O_k, torna-se inviável efetuar uma computação exata de ciclos hamiltonianos nestes grafos. Consequentemente, até agora, somente para k<14 é conhecido que O_k é hamiltoniano.

Metodologia

A pesquisa se baseou fundamentalmente em teoria matemática e computacional, assim a metodologia consistiu: (a) no estudo de conceitos e propriedades de teoria dos grafos em bibliografia recomendada e de artigos científicos relacionados ao problema; (b) na sistematização dos resultados através de relatórios; (c) em reuniões e seminários semanais.

Resultados

Determinamos alguns resultados teóricos inéditos na literatura. Provamos que:

1. Se existe um ciclo ou caminho hamiltoniano em O_k-1, então existe um ciclo C' em O_k tal que |C'| >= 50% do número de vértices de O_k.

2. Se existe um ciclo hamiltoniano em O_k-1, então existe um ciclo C' em O_k tal que |C'| >= 75% do número de vértices de O_k.

3. Existe um ciclo hamiltoniano em O_k-1 se e somente se existe uma sequência R dos vértices de O_k tal que nem 1 nem n pertencem aos vértices de R e o tamanho da interseção entre o primeiro e o ultimo vértice ou quaisquer dois vértices consecutivos é 1.

Conclusão

O primeiro resultado fornece um ciclo com 50% dos vértices para O₁₈, desde que é conhecido um caminho hamiltoniano em O₁₇. O segundo resultado fornece um ciclo com 75% dos vértices em O₁₄, desde que é conhecido um ciclo hamiltoniano em O₁₃. O terceiro resultado fornece uma nova formulação do problema que pode facilitar sua resolução, através da utilização de recursos combinatórios de enumeração.