Use este identificador para citar ou linkar para este item: https://repositorio.ufms.br/handle/123456789/464
Tipo: Dissertação
Título: O problema da orientação pfaffiana de grafos
Autor(es): Santos, Fábio Andreatta
Abstract: Um circuito C em um grafo G é alternado se existe um emparelhamento perfeito M de G tal que C é M-alternado. Uma orientação das arestas de um grafo G é uma orientação pfaffiana se, ao percorrermos qualquer circuito alternado em algum sentido, encontramos um número ímpar de arestas orientadas neste mesmo sentido, ou seja, todos os circuitos alternados do grafo possuem paridade ímpar. Se um grafo possui uma orientação pfaffiana, então dizemos que ele é pfaffiano. Nem todo grafo é pfaffiano, como por exemplo o grafo de Petersen e o K3;3. Por isso, decidir se um dado grafo possui, ou não, uma orientação pfaffiana é um problema de grande importância, pois, além de estar relacionado com alguns problemas fundamentais na teoria dos grafos, como determinar o número de emparelhamentos perfeitos em um grafo1, são foi resolvido para algumas classes de grafos: grafos planares, grafos bipartidos, grafos quase-bipartidos e grafos sólidos. Neste trabalho, estudaremos a caracterização do problema da orientação pfaffiana de grafos paras as classes de grafos bipartidos e planares. Além disso, estudaremos parte da teoria de grafos cobertos por emparelhamentos para apresentar uma nova demostração de uma caracterização de grafos pfaffianos dada por Lovász e Plummer em [9].
A circuit C in a graph G is alternating if there is a perfect matching M of G such that C is M-alternating. An orientation of the edges of a graph G is Pfaffian if, regardless of the sense of transversal of any alternating circuit, the number of forward edges is odd. In other words, every alternating circuit of G is oddly oriented. If a graph G admits a Pfaffian orientation, then we say that G is Pfaffian. But not every graph is Pfaffian, as well as Petersen graph and K3;3. That's why deciding if a given graph has, or not, a Pfaffian orientation is a relevant problem related to some fundamental problems in graphs theory, like to determine the number of perfect matching in a graph2, and it was solved for only four classes of graphs: planar graphs, bipartite graphs, near-bipartite graphs and solid graphs. In this work, we study caracterizations to the pfaffian orientation problem for bipartite and planar graphs, as well as part of matching covered graphs theory, which one we use to present a new proof of a caracterization of Pfaffian graphs due to Lovasz and Plummer in [9].
Palavras-chave: Pfaffianos
Teoria dos Grafos
Equações Diferenciais Parciais Elíticas-Parabólicas Quasilineares
Tipo de Acesso: Acesso Aberto
URI: https://repositorio.ufms.br/handle/123456789/464
Data do documento: 2008
Aparece nas coleções:Programa de Pós-graduação em Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
Fabio Andreatta Santos.pdf801,94 kBAdobe PDFThumbnail
Visualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.