metadata.dc.type:	Relatório de Pesquisa
Title:	Sobre problemas clássicos em grafos sob restrições disjuntivas
metadata.dc.creator:	Ayan Perez de Abeu
metadata.dc.contributor.advisor1:	Rosiane de Freitas Rodrigues
metadata.dc.description.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.
Keywords:	Algoritmos Otimização combinatória Teoria dos grafos
metadata.dc.subject.cnpq:	CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO
metadata.dc.language:	pt_BR
metadata.dc.publisher.country:	Brasil
Publisher:	Universidade Federal do Amazonas
metadata.dc.publisher.initials:	UFAM
metadata.dc.publisher.department:	Ciências da Computação Instituto de Ciências Exatas
metadata.dc.publisher.program:	PROGRAMA PIBIC 2014
metadata.dc.rights:	Acesso Aberto
URI:	http://riu.ufam.edu.br/handle/prefix/4848
Issue Date:	31-Jul-2015
Appears in Collections:	Relatórios finais de Iniciação Científica - Ciências Exatas e da Terra

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.