Busca avançada
Ano de início
Entree

O problema do caminho mínimo e suas variantes

Processo: 19/09476-4
Linha de fomento:Bolsas no Brasil - Iniciação Científica
Vigência (Início): 01 de junho de 2019
Vigência (Término): 31 de maio de 2020
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Matemática da Computação
Pesquisador responsável:Carlos Eduardo Ferreira
Beneficiário:Thiago Lima Oliveira
Instituição-sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
Assunto(s):Teoria dos grafos   Otimização combinatória   Trajetória

Resumo

Dentro da área de combinatória e teoria dos grafos um problema conhecido é o problema do caminho mínimo, ou seja, dado um grafo e dois vértices pertencentes a ele encontre o menor caminho entre os dois vértices. Em uma notação matemática o problema pode ser descrito como: dado um grafo G = (V, A) e dois vértices s e t tal que s, t pertencem a V e uma função custo c de A para os inteiros, queremos encontrar um conjunto de arestas S que leva de s a t tal que o somatório dos custos das arestas pertencentes a s seja mínimo. Este problema surge naturalmente em diversas áreas, como no cálculo da rota entre duas cidades ou na maneira de distribuir dados em uma rede de computadores, por isso este tema é de relevância na área. Neste trabalho será estudado além do problema do caminho mínimo, variações deste, como quando incluímos restrições ao número de arestas no caminho, ou outras. Por exemplo, no caminho S encontrado, adicionamos uma função R, das arestas para os inteiros, e colocamos a condição de que a soma de todos R(e) para todo e pertencente a S seja menor que um dado M. Também será analisado o caso em que é interessante procurar não somente o menor mas os K menores caminhos entre dois vértices. Este projeto será desenvolvido ao longo de 12 meses e o objetivo é aprender sobre o problema dos caminhos mínimos, pretendemos assim melhorar a base teórica e computacional em teoria dos grafos do aluno. Serão realizadas também reuniões semanais com o orientador para avaliar o desenvolvimento do projeto e tirar eventuais dúvidas.