Show simple item record

dc.contributor.advisorGuedes, Andre Luiz Pires, 1966-pt_BR
dc.contributor.authorSilva, Murilo Vicente Gonçalves dapt_BR
dc.contributor.otherUniversidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Informáticapt_BR
dc.date.accessioned2017-09-05T20:56:49Z
dc.date.available2017-09-05T20:56:49Z
dc.date.issued2004pt_BR
dc.identifier.urihttp://hdl.handle.net/1884/48885
dc.descriptionOrientador : Prof. André Luiz Pires Guedespt_BR
dc.descriptionDissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 26/08/2004pt_BR
dc.descriptionInclui referências : f. 65-67pt_BR
dc.description.abstractResumo: Esta dissertação apresenta e discute os dois recentemente descobertos algoritmos de teste de perfeição de grafos. A parte central dos dois algoritmos e a mesma. Este núcleo que os dois algoritmos compartilham, que certamente e a parte mais complexa dos mesmos, foi discutido detalhadamente e implementado. Ate o momento, o autor desta dissertação não tem notícias de outras implementações destes algoritmos. A apresentação do algoritmo foi dividida em três partes distintas. A primeira parte agrupa vários algoritmos que testam pela presença de subgrafos específicos. A segunda parte estuda em detalhes o núcleo que os dois algoritmos compartilham. A terceira parte apresenta os dois algoritmos de teste de perfeição de grafos propriamente ditos. Adicionalmente, nesta dissertação foram definidos quatro parâmetros que podem ser associados a um grafo para exprimir seu grau de imperfeição. Estes parâmetros foram denotados p 1, p2, p3 e p4. O autor relacionou estes parâmetros com algumas operações que podem ser aplicadas a um grafo imperfeito para torna-lo perfeito. As operações utilizadas para definir estes parâmetros de foram a remoção de arestas do grafo (pi), a inversão de arestas no grafo (p2), a execução de remoção e inserção de arestas no grafo (p 3) e, finalmente, a remoção de vértices do grafo (p4). Mostrou-se que para qualquer grafo temos p4 < p3 < p1 e p4 < p3 < p2. Alem disso foram apresentados exemplos de grafos em que cada uma destas desigualdades pode ser estrita. O autor apresentou também alguns limitantes inferiores e superiores para estes parâmetros. Finalmente, utilizando um dos limitantes inferiores para p4, mostrou-se que existem grafos que são "bastante imperfeitos" . Mais especificamente, foi demonstrado que existem grafos com n vértices para os quais o número de vértices que deve ser removido n para tornás-lo perfeitos é pelo menos --;- - - lg (2n ). lg (2n) Palavras-chave: teoria dos grafos, algoritmos, teoria algorítmica dos grafos, grafos perfeitos, otimização combinatória.pt_BR
dc.description.abstractAbstract: This dissertation presents and discusses two recently discovered algorithms th a t test if a graph is perfect. The core shared by the two algorithms is discussed in details and the results of its implementation are presented. It is worthwhile to mention th a t no other similar implementation is known so far. The presentation of the algorithms is divided into three parts. The first part presents several algorithms th a t test some particular subgraphs. The second part reviews the core of the algorithms and the third part presents the two algorithms for perfectness. Additionally, in this work it is defined four parameters th a t can measure how imperfect a graph is. These parameters are denoted p1, p2, p3 and p4. The defined parameters are related to some operations th a t can be applied to a graph to make it perfect. The following operations are considered: edge deletion (pi), edge insertion (p2), both deletion and insertion of edges (p 3) and, finally, vertex deletion (p4). It is shown th a t for any graph it holds th a t p4 < p3 < p 1 and p4 < p3 < p2. It is also shown examples of graphs where such inequalities are strict. Finally, some lower bounds and upper bounds for these paramenters are shown. As a consequence of a lower bound for p4 , the author shows th a t there are "highly" imperfect graphs. More precisely, there are graphs with n vertices where n , . . Keywords: graph theory, algorithms, algorithmic graph theory, perfect graphs, combinatorial optimization.pt_BR
dc.format.extent67 f. : il.pt_BR
dc.format.mimetypeapplication/pdfpt_BR
dc.languagePortuguêspt_BR
dc.relationDisponível em formato digitalpt_BR
dc.subjectCiência da computaçãopt_BR
dc.titleAlgoritmos para teste de perfeição de grafospt_BR
dc.typeDissertaçãopt_BR


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record