Aplicação do Teorema de Dirac na identificação de ciclos hamiltonianos em grafos completos e bipartidos

uma análise computacional

Resumo

Este trabalho apresenta uma análise computacional da aplicação do Teorema de Dirac para identificação de ciclos hamiltonianos em diferentes classes de grafos. O estudo utilizou implementações em Python com a biblioteca NetworkX para examinar as propriedades estruturais de grafos completos e grafos bipartidos, verificando as condições estabelecidas pelo teorema proposto por Gabriel Andrew Dirac em 1952. Os resultados demonstraram que grafos completos K₆ satisfazem consistentemente as condições do teorema (δ ≥ n/2), garantindo a existência de ciclos hamiltonianos, enquanto grafos bipartidos completos K₄,₅ não satisfazem tais condições devido às suas propriedades estruturais inerentes. A metodologia empregada permitiu uma visualização das diferenças topológicas entre as duas classes de grafos e confirmou computacionalmente as previsões teóricas. Os achados contribuem para o entendimento da aplicabilidade do Teorema de Dirac e suas limitações em diferentes estruturas de grafos, fornecendo insights valiosos para problemas de otimização em redes e teoria dos grafos aplicada.​