Decomposição otima em orelhas para grafos matching covered
Marcelo H. Carvalho
TESE
Português
T/UNICAMP C253d
Campinas, SP : [s.n.], 1997.
166f. : il.
Orientador: Claudio L. Lucchesi
Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação
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...
Ver mais
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.
Ver menos
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...
Ver mais
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.
Ver menos
Lucchesi, Cláudio Leonardo, 1945-
Orientador
Murty, Uppaluri Silva Ramachandra
Avaliador
Mandel, Arnaldo
Avaliador
Kohayakawa, Yoshihraru
Avaliador
Meidanis, João, 1960-
Avaliador
Decomposição otima em orelhas para grafos matching covered
Marcelo H. Carvalho
Decomposição otima em orelhas para grafos matching covered
Marcelo H. Carvalho
Exemplares
Nº de exemplares: 2
Não existem reservas para esta obra