Return to search

Decomposição otima em orelhas para grafos matching covered

Orientador: Claudio L. Lucchesi / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-22T14:37:46Z (GMT). No. of bitstreams: 1
Carvalho_MarceloH_D.pdf: 3472839 bytes, checksum: 604447ee0052ba3daa1a6900cea3c290 (MD5)
Previous issue date: 1997 / Resumo: O assunto do qual se trata este trabalho se insere na área de teoria dos grafos, e mais especificamente de grafos matching covered, que são grafos conexos em que toda aresta pertence a um emparelhamento perfeito. L. Lovász desenvolveu toda a base da teoria dos grafos matching covered e, como conseqüência, obteve uma caracterização para o matching lattice. Desta caracterização foi possível obter uma prova para uma relaxação da conjectura de Tutte que generaliza o problema das quatro cores. Existem dois procedimentos de decomposição de grafos matching covered que são fundamentais: um deles é a decomposição em cortes justos e o outro é a decomposição em orelhas. Para uma decomposição em orelhas podem ser usadas orelhas simples ou duplas. Uma importante questão é determinar o número mínimo de orelhas duplas de uma decomposição em orelhas de um grafo matching covered. Neste trabalho apresentamos uma resposta para esta questão. Apresentamos também duas conseqüências desta solução: uma delas é que existe uma base para o matching lattice formada apenas por emparelhamentos perfeitos, e a outra é uma caracterização para o Lin(M, Z2 ). Esta última nos permite obter uma prova para outra relaxação da conjectura de Tutte. / Abstract: Matching covered graphs are connected graphs in which every edge lies in a perfect matching. The base of this theory was developed by L. Lovász, and as consequence, a characterization to the matching lattice was obtained. Then it was possible to obtain a proof for a relaxation of a conjecture of Tutte, which is related to the four colors problem. There are two main 'decomposition procedures of a matching covered graph: tight cuts decomposition and ear decomposition. For ear decomposition one can use single or double ears. One important question asks about the minimum number of double ears of any ear decomposition of such graphs. This work gives an answer to this question It is also presented two consequences: that there is a base for the matching lattice formed solely by incidence vectors of perfect matching, and a characterization to Lin (M, Z2 ) which gives a proof to an other relaxation of the Tutte conjecture. / Doutorado / Doutor em Ciência da Computação

Identiferoai:union.ndltd.org:IBICT/oai:repositorio.unicamp.br:REPOSIP/276045
Date13 December 1996
CreatorsCarvalho, Marcelo H
ContributorsUNIVERSIDADE ESTADUAL DE CAMPINAS, Lucchesi, Cláudio Leonardo, 1945-, Luchesi, Claudio Leonardo, Murty, Uppaluri Silva Ramachandra, Mandel, Arnaldo, Kohayakawa, Yoshihraru, Meidanis, João
Publisher[s.n.], Universidade Estadual de Campinas. Instituto de Computação, Programa de Pós-Gradução em Ciência da Computação
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguagePortuguese
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis
Format166f. : il., 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.0018 seconds