Return to search

Sobre grafos perfeitos

Orientador : Claudio L. Lucchesi / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-15T05:25:59Z (GMT). No. of bitstreams: 1
MendoncaNeto_CandidoFerreiraXavierde_M.pdf: 1216674 bytes, checksum: 8e85895a8cb7f162a8e6807b1c063822 (MD5)
Previous issue date: 1987 / Resumo: O primeiro capítulo introduz a noção de grafos perfeitos e as antigas conjeturas de Berge. A primeira delas, demontrada por Lovász, consta do capítulo 1 com o nome de Teorema dos Grafos Perfeitos. O segundo capítulo apresenta propriedades fundamentais dos grafos críticos (i. é, imperfeitos minimais) e os chamados grafos particionáveis. O capítulo termina com a apresentação dos grafos de cliques máximos de Tucker. O terceiro e último capítulo apresenta uma variada coleção de classes de grafos perfeitos. Foi consegui da uma tênue unificação de algumas dessas classes. O apêndice considera a segunda conjetura, a chamada conjetura "forte", e apresenta um resumo de algumas classes para as quais a conjetura vale / Abstract: The first chapter introduces the notion of perfect graphs and Berge's old conjecture, proved by Lovász, appears in chapter 1 under the name or Perfect Graphs Theorem. The second chapter presents fundamental properties of critical graphs (i. e., minimal imperfect graphs) and the so-called partitionable graphs. The chapter concludes with a presentation of Tucker's maximum clique graphs. The third and the last chapter presents a broad colection or classes of perfect graphs. The chapter presents a weak unification or these classes. The appendix analyzes the second conjecture, the so-called "strong" conjecture, and presents a survey of some classes over which this conjecture holds / Mestrado / Mestre em Ciência da Computação

Identiferoai:union.ndltd.org:IBICT/oai:repositorio.unicamp.br:REPOSIP/276119
Date20 August 1987
CreatorsMendonça Neto, Candido Ferreira Xavier de, 1959-
ContributorsUNIVERSIDADE ESTADUAL DE CAMPINAS, Lucchesi, Cláudio Leonardo, 1945-
Publisher[s.n.], Universidade Estadual de Campinas. Instituto de Matemática, Estatística e Ciência da Computação, Programa de Pós-Graduação em Ciência da Computação
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguagePortuguese
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis
Format53f., application/octet-stream
Sourcereponame:Repositório Institucional da Unicamp, instname:Universidade Estadual de Campinas, instacron:UNICAMP
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0022 seconds