Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/276045
Type: TESE
Title: Decomposição otima em orelhas para grafos matching covered
Author: Carvalho, Marcelo H
Advisor: Lucchesi, Cláudio Leonardo, 1945-
Luchesi, Claudio Leonardo
Abstract: 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.
Subject: Teoria dos grafos
Teoria dos grafos - Processamento de dados
Language: Português
Editor: [s.n.]
Date Issue: 1997
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Carvalho_MarceloH_D.pdf3.39 MBAdobe PDFView/Open


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