En teoría de grafos , una orientación pfaffiana de un grafo no dirigido asigna una dirección a cada arista, de modo que ciertos ciclos (los "ciclos centrales pares") tienen un número impar de aristas en cada dirección. Cuando un grafo tiene una orientación pfaffiana, la orientación se puede utilizar para contar las coincidencias perfectas del grafo. Esta es la idea principal detrás del algoritmo FKT para contar las coincidencias perfectas en grafos planares , que siempre tienen orientaciones pfaffianas. De manera más general, todo grafo que no tiene el grafo de utilidad como grafo menor tiene una orientación pfaffiana, pero no la tiene, ni tampoco la tienen infinitos otros grafos no pfaffianos mínimos.
Una orientación pfaffiana de un grafo no dirigido es una orientación en la que cada ciclo central par tiene una orientación impar. Los términos de esta definición tienen los siguientes significados:
Las orientaciones de Pfaffian se han estudiado en relación con el algoritmo FKT para contar el número de emparejamientos perfectos en un gráfico determinado. En este algoritmo, las orientaciones de los bordes se utilizan para asignar los valores a las variables en la matriz de Tutte del gráfico. Luego, el Pfaffian de esta matriz (la raíz cuadrada de su determinante ) proporciona el número de emparejamientos perfectos. Cada emparejamiento perfecto contribuye al Pfaffian independientemente de la orientación que se utilice; la elección de una orientación Pfaffian garantiza que todas estas contribuciones tengan el mismo signo, de modo que ninguna de ellas se cancele. Este resultado contrasta con la complejidad computacional mucho mayor de contar emparejamientos en gráficos arbitrarios. [2]
Se dice que un grafo es pfaffiano si tiene una orientación pfaffiana. Todo grafo plano es pfaffiano. [3] Una orientación en la que cada cara de un grafo plano tiene un número impar de aristas orientadas en el sentido de las agujas del reloj es automáticamente pfaffiana. Tal orientación se puede encontrar comenzando con una orientación arbitraria de un árbol de expansión del grafo. Las aristas restantes, que no están en este árbol, forman un árbol de expansión del grafo dual , y sus orientaciones se pueden elegir de acuerdo con un recorrido de abajo hacia arriba del árbol de expansión dual para garantizar que cada cara del grafo original tenga un número impar de aristas en el sentido de las agujas del reloj. [4]
En términos más generales, cada grafo sin -menores tiene una orientación pfaffiana. Estos son los grafos que no tienen como menor al grafo de utilidad (que no es pfaffiano) . Por el teorema de Wagner , los grafos sin -menores se forman pegando copias de grafos planares y el grafo completo a lo largo de aristas compartidas. La misma estructura de pegado se puede utilizar para obtener una orientación pfaffiana para estos grafos. [4]
Junto con , hay infinitos grafos no pfaffianos mínimos. [1] Para grafos bipartitos , es posible determinar si existe una orientación pfaffiana y, de ser así, encontrarla, en tiempo polinomial . [5]
