CICLOS HAMILTONIANOS EM GRAFOS

Marcelo de Souza Santos

Abstract


Neste trabalho tratamos de um problema clássico bem conhecido em Teoria dos Grafos: o problema da existência de um ciclo hamiltoniano. Um grafo é dito hamiltoniano se possui um ciclo hamiltoniano, ou seja, apresenta um ciclo que percorre todos os vértices do grafo. Estudamos problemas clássicos associados a este problema em termos do número de arestas, do grau mínimo e da sequência de graus dos vértices de um grafo. Além disso, estudamos resultados espectrais para o problema de hamiltonicidade referentes às matrizes de adjacências e laplaciana. A principal contribuição deste trabalho é a apresentação detalhada de condições suficientes e condições necessárias que garantem um ciclo hamiltoniano em um grafo já existentes na bibliografia.


Keywords


Ciclos hamiltonianos; Teoria Espectral de Grafos; Grafos.



DOI: https://doi.org/10.5902/2179460X24502

Refbacks

  • There are currently no refbacks.


Copyright (c) 2017 Ciência e Natura



Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.