Orientações pfaffianas e o furtivo grafo de Heawood / Pfaffian orientations and the elusive Heawood graph

AUTOR(ES)
DATA DE PUBLICAÇÃO

2006

RESUMO

A graph G that contains a perfect matching is Pfaffiano if there is an orientation D of the edges of G, such that every conformal circuit of G is oddly oriented in D. A subgraph H of G is conformal if G - V (H) has a perfect matching. A circuit with an even number of edges is oddly oriented if the number of edges whose orientation in D agrees with any sense of traversal of the circuit is odd. Counting the number of perfect matchings of a graph is known to be NP-hard [11, page 307]. However, when restricted to Pfaffiano graphs, this problem is solvable in polynomial time [11, page 319]. The characterisation of Pfaffiano bipartite graphs, achieved by Charles Little, is almost thirty years old [9]. However, only recently, polynomial time algorithms for determining whether a bipartite graph is Pfaffiano were discovered, by McCuaig [13] and independently by Robertson, Seymour and Thomas [14]. This problem s solution solves a lot of problems, some of them are quite famous, in graph theory, economy and chemistry, as described in McCuaig s article [13, pages 16 to 35]. On this dissertation, we present a new proof of the correctness of this algorithm distinct from the two previously known proofs

ASSUNTO(S)

teoria dos casamentos algoritmos algorithms teoria dos grafos matching theory graph theory

ACESSO AO ARTIGO

Documentos Relacionados