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
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.unicamp.br:REPOSIP/276045 |
| Date | 13 December 1996 |
| Creators | Carvalho, Marcelo H |
| Contributors | UNIVERSIDADE 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 Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | 166f. : il., application/octet-stream |
| Source | reponame:Repositório Institucional da Unicamp, instname:Universidade Estadual de Campinas, instacron:UNICAMP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0019 seconds