Análise computacional da condição de Ore e identificação de ciclos hamiltonianos em grafos aleatórios
DOI:
https://doi.org/10.47385/tudoeciencia.2547.2025Palavras-chave:
Teoria dos Grafos. Condição de Ore. Ciclos Hamiltonianos. Algoritmos. Simulação Computacional.Resumo
A teoria dos grafos constitui um ramo fundamental da matemática discreta com amplas aplicações em ciência da computação, engenharia e outras áreas. Este trabalho apresenta uma análise computacional da condição de Ore para a existência de ciclos hamiltonianos em grafos. O teorema de Ore, proposto em 1960, estabelece uma condição suficiente para garantir a existência de um ciclo hamiltoniano em um grafo. Através de simulações computacionais utilizando a linguagem Python e as bibliotecas NetworkX e Matplotlib, foi desenvolvido um algoritmo que gera grafos aleatórios satisfazendo a condição de Ore e verifica empiricamente a presença de ciclos hamiltonianos. Os resultados obtidos demonstram a eficácia do teorema de Ore como critério suficiente para a hamiltonicidade, evidenciando que todos os grafos gerados que satisfazem a condição apresentaram ciclos hamiltonianos verificáveis. A metodologia empregada combina geração probabilística de grafos com busca exaustiva por permutações, oferecendo uma abordagem prática para o estudo desta importante propriedade estrutural em grafos. As implicações deste estudo estendem-se a problemas de otimização em redes, design de circuitos e análise de sistemas complexos.
Downloads
Referências
APPLEGATE, D. L. et al. The traveling salesman problem: a computational study. Princeton: Princeton University Press, 2007.
BONDY, J. A.; MURTY, U. S. R. Graph theory. London: Springer, 2008.
CHARTRAND, G.; LESNIAK, L. Graphs & digraphs. 4. ed. Boca Raton: Chapman & Hall/CRC, 2005.
DIRAC, G. A. Some theorems on abstract graphs. Proceedings of the London Mathematical Society, v. 2, n. 1, p. 69-81, 1952.
ERDŐS, P.; RÉNYI, A. On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences, v. 5, p. 17-61, 1960.
FRUCHTERMAN, T. M.; REINGOLD, E. M. Graph drawing by force-directed placement. Software: Practice and Experience, v. 21, n. 11, p. 1129-1164, 1991.
GAREY, M. R.; JOHNSON, D. S. Computers and intractability: a guide to the theory of NP-completeness. New York: W. H. Freeman, 1979.
KARP, R. M. Reducibility among combinatorial problems. In: MILLER, R. E.; THATCHER, J. W. (Ed.). Complexity of computer computations. New York: Plenum Press, 1972. p. 85-103.
KORTE, B.; VYGEN, J. Combinatorial optimization: theory and algorithms. 6. ed. Berlin: Springer, 2018.
ORE, O. Note on Hamilton circuits. The American Mathematical Monthly, v. 67, n. 1, p. 55, 1960.
RAHMAN, M. S.; KAYKOBAD, M. On Hamiltonian cycles and Hamiltonian paths. Information Processing Letters, v. 94, n. 1, p. 37-41, 2005.
Downloads
Publicado
Como Citar
Edição
Seção
Licença
Copyright (c) 2025 Tudo é Ciência: Congresso Brasileiro de Ciências e Saberes Multidisciplinares
Este trabalho está licenciado sob uma licença Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
