On paths and trails in edge-colored graphs and digraphs - Lyra, Adria Ramos de (2023)
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-diﬁculdade 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