CONVEXIDADE EM GRAFOS

XXXVII Encontro de Iniciação Científica

Hedilandio Vidal Araujo, PEDRO SANTOS MOTA e ARRAES, Julio Cesar Silva Araujo

Este resumo trata das atividades desenvolvidas em 2017/2018 pelos estudantes de Matemática da UFC, Pedro Arraes e Hedilandio Vidal, sob orientação do Prof. Dr. Júlio César Silva Araújo cujo ramo estudado é a Teoria dos Grafos, mais especificamente Convexidade em Grafos. No período o bolsista Pedro, obteve alguns resultados sobre convexidade em grafos orientados, referente ao número de envoltória, a saber, três resultados: para torneios (uma classe de grafos orientados) encontramos um limitante apertado, mostramos a composição de um conjunto de envoltória mínimo para grafos cactos orientados, e para grafos bipartidos orientados demonstramos que o problema envolvendo esse parâmetro é difícil do ponto de vista computacional. Quanto ao bolsista Hedilandio, inicialmente o objetivo da bolsa era o estudo da Convexidade em Grafos, porém, dada a complexidade e especificidade de tal tema, somados ao desconhecimento do bolsista em tal área, o orientador optou por introduzir ao orientando os conceitos necessários para o estudo mais avançado. Os assuntos contemplados foram os seguintes: Definição de grafo, Isomorfismo, Caminhos, Ciclos, Trilhas, Grafos Bipartidos, Árvores, Problemas extremais e Emparelhamentos. O orientando procurava por exemplos do cotidiano que poderia utilizar os grafos como modelos matemáticos para a solução. Neste processo, os temas de maior enfoque foram; Teorema de Turán, Algoritmo de Dijkstra e Teorema de Hall. Durante o curto período de 4 meses de bolsa do CNPq o bolsista pôde escrever sua monografia que abordava o tema: Aplicação da Teoria dos Grafos à Resolução de Problemas. Deixo meus agradecimentos ao órgão financiador, CNPq, pelo investimento e incentivo dado a pesquisa científica.

Palavras-chave: Grafos. Convexidade. Grafos Orientados. Otimização.

Encontros Universitários da UFC, Fortaleza, v. 3, 2018

1182