Trabalho Final de Graduação

Informações dos Participantes

Nomes: Nathan Luiz Bezerra Martins e Willian Miura Mori

Orientadora: Profª. Drª. Yoshiko Wakabayashi

Resumo

Seja 𝑛 ≥ 3 e 𝐺 = 𝐺1 ∪ 𝐺2 ∪ … ∪ 𝐺𝑛 um grafo que é a união de 𝑛 grafos simples dois a dois aresta- disjuntos 𝐺𝑖 de ordem 𝑛, todos definidos sobre um mesmo conjunto de vértices, cada qual com arestas monocromaticamente coloridas mas coletivamente usando 𝑛 cores distintas. Joos and Kim (2020) provou que se cada 𝐺𝑖 satisfaz a condição de Dirac (i.e. tem grau mínimo pelo menos 𝑛/2), então 𝐺 tem um circuito Hamiltonian rainbow (um circuito em que todas as arestas têm cores distintas). Nesta monografia apresentamos uma versão algoritmica dessa prova, e explicamos passo a passo um algoritmo que constrói um circuito Hamiltoniano rainbow em 𝐺. Apresentamos um pseudocódigo para cada procedimento que é descrito, detalhando as estruturas que são usadas e analisando sua complexidade computacional. Mostramos que o algoritmo que implementamos tem complexidade 𝑂(𝑛^3), assintoticamente a melhor complexidade possível, pois o grafo de entrada 𝐺 tem 𝑂(𝑛^3) arestas. Adicionalmente, incluímos neste trabalho uma animação gráfica que criamos para ilustrar o processo de construção de um circuito Hamiltoniano rainbow no grafo 𝐺.

Monografia

Referências

• Dirac, G. A. *Some Theorems on Abstract Graphs*. Proceedings of the London Mathematical Society, 1952. DOI: 10.1112/plms/s3-2.1.69.
• Joos, Felix e Kim, Jaehoon. *On a rainbow version of Dirac’s theorem*. Bulletin of the London Mathematical Society, 2020, vol. 52, pp. 498–504. DOI: 10.1112/blms.12343.
• Clinch, Katie; Goerner, Jackson; Huynh, Tony; Illingworth, Freddie. *Notes on Aharoni's rainbow cycle conjecture*. arXiv, 2022. Disponível em: https://arxiv.org/abs/2211.07897.
• Nathanson, Melvyn B. *The Caccetta-Haggkvist conjecture and additive number theory*. arXiv, 2006. Disponível em: https://arxiv.org/abs/math/0603469.