Este projeto de pesquisa envolve problemas clássicos em grafos bem resolvidos computacionalmente, ou seja, problemas pertencentes à classe P de complexidade computacional, para os quais existe pelo menos um algoritmo para cada problema que o resolve na otimalidade em tempo polinomial de processamento. Exemplos de tais problemas clássicos são: problema da árvore geradora mínima (do inglês, minimum spanning tree); prolema do emparelhamento máximo (do inglês, maximum matching); problema do caminho mínimo (do inglês, shortest path problem); dentre váios outros. O interesse deste projeto é o de investigar variações de tais problemas que envolvem restrições adicionais, ou seja, variantes sob restrições disjuntivas, positivas ou negativas. Isto envolve o levantamento dos resultados existentes para diversas classes de grafos existentes, bem como grafos cíclicos, bipartidos, completos, caminhos, entre outros, com o intuito de se refazer provas, algoritmos e de encontrar um ponto de contribuição.
Um grafo é um par ordenado G=(V,E), onde V é um conjunto de n elementos denominados de vértices, e E é um conjunto de m pares não ordenados de elementos de V, denominados de arestas. Restrições disjuntivas em problemas clássicos em teoria dos grafos podem ser do tipo negativas ou positivas. Onde as restrições disjuntivas negativas obedecem a regra de que há incompatibilidade entre um par de arestas, e que esse par de arestas não podem pertencer simultaneamente a uma solução viável. E as restrições disjuntivas positivas respeitam o princípio de que pelo menos uma aresta de um dado par de arestas proposto devem compor uma solução viável.
Partindo dos conceitos apresentados é comum de se ver problemas modelados nesses tipos de estruturas, tal como o problema de casamentos estáveis, que consiste em casar n homens com n mulheres de modo que cada homem ordene as n mulheres em ordem de preferência, e cada mulher faça o mesmo com os homens. E um casamento (homem, mulher) é denominado estável se não está incluso no conjunto dos pares (homem, mulher) onde a mulher prefere o homem à seu esposo atual, e o homem prefere a mulher à sua esposa atual. Para esse problema existe um algoritmo de Gale-Shapley, que encontra um casamento particular em tempo polinomial tal que pode ser especificado. Além desse problema, existem inúmeros outros que se modelam com essa estrutura de grafos com restrições disjuntivas, tal como casamentos estáveis com casais proibidos [FONSECA, 2000], colocação de professores [TOMÀS, 2005], programação de operações com restrições disjuntivas, entre outros.
|
