Detalhes bibliográficos
| Ano de defesa: |
2023 |
| Autor(a) principal: |
Lyra, Adria Ramos de |
| Orientador(a): |
Não Informado pela instituição |
| Banca de defesa: |
Não Informado pela instituição |
| Tipo de documento: |
Tese
|
| Tipo de acesso: |
Acesso aberto |
| Idioma: |
eng |
| Instituição de defesa: |
Não Informado pela instituição
|
| Programa de Pós-Graduação: |
Não Informado pela instituição
|
| Departamento: |
Não Informado pela instituição
|
| País: |
Não Informado pela instituição
|
| Palavras-chave em Português: |
|
| Link de acesso: |
http://app.uff.br/riuff/handle/1/30999
|
Resumo: |
Neste trabalho, estuda-se diferentes questões sobre s-t caminhos e trilhas propriamente coloridos em grafos e digrafos com cores nas aretas. Dado Gc um grafo com c cores nas aretas sem trilhas fechadas propriamente coloridas, apresenta-se um procedimento polinomial para determinação de s-t trilhas propriamente coloridas que visitam todos os vértices de Gc um determinado número de vezes. Como consequência imediata, resolve-se polinomialmente o problema do caminho Hamiltoniano e Euleriano para esta classe particular de grafos. Além disso, prova-se que encontrar dois caminhos propriamente coloridos disjuntos por vértices ou arestas em Gc contendo no máximo L > 0 arestas é NP-completo forte. Também, mostra-se que achar dois caminhos monocromáticos disjuntos por vértices, com cores diferentes, em um grafo Gc qualquer é NP-completo. Considerando digrafos com cores nas arestas, mostra-se que determinar um s-t caminho direcionado propriamente colorido é NP-completo mesmo para c = (n2). Se o digrafo for um torneio com cores nas arestas, mostra-se que decidir se este contém um circuito propriamente colorido passando por um vértice v (ou um caminho Hamiltoniano direcionado) é NP-completo. Como consequência, resolve-se uma versão mais fraca de um problema proposto em [30]. Além disso, considerando-se trilhas ao invés de caminhos, mostra-se que alguns problemas são polinomiais para s-t trilhas direcionadas propriamente coloridas. Considera-se também s-t caminhos, trilhas e passeios em grafos coloridos com custos de conexão entre as aretas. Sempre que se muda de uma cor para outra em um passeio tem-se um custo de conexão ri,j associado, onde i e j são as cores das sucessivas arestas do passeio. O objetivo é encontrar uma rota cujo custo total de conexão seja minimizado. Algoritmos polinomiais e provas de NP-dificuldade são apresentados para casos particulares: quando a desigualdade triangular é satifeita ou não, quando os custos de conexões são simétricos (i.e., ri,j = rj,i) ou assimétricos. Também são investigados instâncias com grau máximo limitado e grafos planares |
