Tipo de documento:	Relatório de Pesquisa
Título:	Sobre problemas clássicos em grafos sob restrições disjuntivas
Autor(a):	Ayan Perez de Abeu
Orientador(a):	Rosiane de Freitas Rodrigues
Resumo:	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.
Palavras-chave:	Algoritmos Otimização combinatória Teoria dos grafos
Área de conhecimento - CNPQ:	CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO
Idioma:	pt_BR
País de publicação:	Brasil
Editor:	Universidade Federal do Amazonas
Sigla da Instituição:	UFAM
Faculdade, Instituto ou Departamento:	Ciências da Computação Instituto de Ciências Exatas
Nome do programa:	PROGRAMA PIBIC 2014
Tipo de acesso:	Acesso Aberto
URI:	http://riu.ufam.edu.br/handle/prefix/4848
Data do documento:	31-jul-2015
Aparece nas coleções:	Relatórios finais de Iniciação Científica - Ciências Exatas e da Terra

Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.