In graph theory, a Pfaffian orientation of an undirected graph assigns a direction to each edge so that certain cycles, called even central cycles, have an odd number of edges pointing in each direction. Such orientations make it possible to count the perfect matchings of a graph, and they underlie the FKT algorithm used for this purpose on planar graphs. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Connections
In Field
Source Wikipedia: Pfaffian orientation
Sources
Wikipedia: Pfaffian orientation
Lead section
In graph theory, a Pfaffian orientation of an undirected graph assigns a direction to each edge, so that certain cycles (the "even central cycles") have an odd number of edges in each direction.
In Group: Planar Graph Algorithms, Introduction
This is the main idea behind the FKT algorithm for counting perfect matchings in planar graphs, which always have Pfaffian orientations.
In Field: Algorithms and Complexity Theory, Lead sentence
Pfaffian orientation of an undirected graph assigns a direction to each edge, so that certain cycles (the "even central cycles") have an odd number of edges in each direction.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.