Resumo
Este projeto visa determinar a classe de complexidade (P, NP, co-NP, NP-completo, etc) de problemas sobre grafos Pfaffianos. Os grafos Pfaffianos são precisamente os grafos cujas arestas podem ser orientadas de tal forma que todo circuito conforme no grafo com um número par de vértices tem orientação ímpar. Não se conhece nenhuma caracterização para grafos Pfaffianos em geral. Sequer se s…