Hiperplanos conexos em matrÃides binÃrias

AUTOR(ES)

Tereza Raquel Brito de Melo

DATA DE PUBLICAÇÃO

2005

RESUMO

Non-separating circuits and cocircuits play an important role in the understanding of the structure of graphic matroids. For example, using this concept Tutte [27] characterized the 3-connected graphs which are planar. Bixby and Cunningham [2] generalized Tutteâs result for the class of binary matroids. Kelmans [11] and, independently, Seymour (see [16]) proved that every simple and cosimple connected binary matroid has a non-separating cocircuit. McNulty and Wu [15] proved that these matroids have at least four non-separating cocircuits. Moreover, this result is sharp. For 3-connected binary matroids, Lemos [14] presented the dimension of the subspace of the cocycle space spanned by the non-separating cocircuits of the matroid avoiding an element. In this thesis we give a lower bound for the dimension of such subspace spanned by the non-separating cocircuits avoiding a set with at least two elements of the matroid. The first Chapter deals with the matroid theory which is used to prove the main results of this thesis. These results are stated in that chapter. In Chapter 2, the problem of finding non-separating cocircuits in a simple and cosimple connected binary matroid is reduced to the problem of finding non-separating cocircuits avoiding a set of elements in some 3-connected binary matroids. In the third Chapter the 3-connected binary matroids without non-separating cocircuits avoiding some set with two elements are characterized. This result is essential for setting a lower bound for the dimension of the subspace of the cocycle space spanned by the non-separating cocircuits avoiding a 2-set of elements of a 3-connected binary matroid. Moreover, the dimension of such subspace is computed when the subset avoided by these cocircuits is a triangle of the matroid. Finally, the dimension of the same subspace is determined for the non-separating cocircuits avoiding any collection of elements in the matroid, if the restriction of the matroid to this set has no coloops

ASSUNTO(S)

simples dimensÃo conexa grafos matematica 3-conexa colaÃo planar planares coloop non-separating cocircuit matroid binary graph simple binÃria co-simples matrÃide connected dimension cocircuito nÃo-separador cosimple 3-connected

Documentos Relacionados

• MatrÃides binÃrias com circunferÃncia 6.
• Cobertura e empacotamento por circuitos atravÃs de um elemento em matrÃides
• PartiÃÃo de matrÃides, conjuntos co-geradores e bridget-it
• Redes Neurais ProbabilÃsticas para ClassificaÃÃo de Imagens BinÃrias
• Resolução de problemas de Bin Packing utilizando rede neural aumentada e Minimum Bin Slack