Busca avançada
Ano de início
Entree

O problema da interseção de caminhos mais longos em classes de grafos

Processo: 12/10252-4
Linha de fomento:Bolsas no Brasil - Iniciação Científica
Vigência (Início): 01 de agosto de 2012
Vigência (Término): 31 de julho de 2013
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Christiane Neme Campos
Beneficiário:Vitor Roberto de Almeida Castro
Instituição-sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
Assunto(s):Teoria dos grafos

Resumo

Este projeto de Iniciação Científica tem por objetivo iniciar o aluno na área de pesquisa em Teoria de Grafos, por meio do estudo da conjetura que afirma que quaisquer três caminhos mais longos em um grafo conexo possuem um vértice em comum. Este problema foi motivado por uma pergunta de T. Gallai em 1968 e aborda aspectos importantes da teoria, como conexidade e etruturas de caminhos. O foco deste projeto é estudar alguns dos desdobramentos da conjetura e investigar a sua validade para classes de grafos.