O problema da orientação pfaffiana de grafos

• Ano de defesa: 2008
• Autor(a) principal: Santos, Fábio Andreatta
• Orientador(a): Carvalho, Marcelo Henriques de
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Palavras-chave em Português: Pfaffianos; Teoria dos Grafos; Equações Diferenciais Parciais Elíticas-Parabólicas Quasilineares
• Link de acesso: https://repositorio.ufms.br/handle/123456789/464

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].