Algorithme FKT

L'idée principale est que chaque terme non nul dans le pfaffien de la matrice d'adjacence d'un graphe G correspond à un couplage parfait. Ainsi, si l'on peut trouver une orientation de G pour aligner tous les signes des termes dans le pfaffien (soit à + soit à - ), alors la valeur absolue du pfaffien est exactement le nombre de couplages parfaits dans G. L'algorithme FKT effectue une telle tâche pour un graphe planaire G. L'orientation qu'il trouve s'appelle une orientation pfaffienne.

Soit G = ( V, E ) un graphe non orienté, et soit A sa matrice d'adjacence. On définit PM ( n ) comme étant l'ensemble des partitions de n éléments en paires. Le nombre de couplages parfaits dans G est donné par :

${\displaystyle \operatorname {CP} (G)=\sum _{M\in PM(|V|)}\prod _{(i,j)\in M}A_{ij}.}$

Le lien avec pfaffien d'une ${\displaystyle n\times n}$-matrice A est le suivant :

${\displaystyle \operatorname {pf} (A)=\sum _{M\in PM(n)}\operatorname {sgn} (M)\prod _{(i,j)\in M}A_{ij},}$

où sgn( M ) est la signature de la permutation M. Une orientation pfaffienne de G est un graphe orienté H avec une matrice d'adjacence B à coefficients (1, 0, -1) telle que pf( B ) = CP( G )[8]. En 1967, Kasteleyn a prouvé que les graphes planaires ont une orientation pfaffienne calculable efficacement. Plus précisément, pour un graphe planaire G, soit H une version orientée de G où un nombre impair d'arêtes sont orientés dans le sens des aiguilles d'une montre pour chaque face dans un plongement planaire de G . Alors H est une orientation Pfaffienne de G .

Enfin, pour toute matrice antisymétrique A ,

${\displaystyle \operatorname {pf} (A)^{2}=\det(A)}$,

où det( A ) est le déterminant de A. Ce résultat est dû à Arthur Cayley[9]. Puisque les déterminants sont calculables efficacement, il en est de même de CP( G ).

1. Calculer un plongement planaire de G .
2. Calculer un arbre couvrant T₁ du graphe d'entrée G .
3. Orienter de façon arbitraire chaque arête de G qui est dans T₁ .
4. Utiliser le plongement planaire pour créer un graphe (non orienté) T₂ avec le même ensemble de sommets que le graphe dual de G .
5. Créer une arête dans T₂ entre deux sommets si leurs faces correspondantes dans G partagent une arête dans G qui n'est pas dans T₁. (On observe que T₂ est un arbre. )
6. Pour chaque feuille v dans T₂ qui n'est pas la racine faire :
   1. Soit e l'arête isolée de G dans la face qui correspond à v et qui n'a pas encore d'orientation.
   2. Donner à e une orientation telle que le nombre d'arêtes orientées dans le sens des aiguilles d'une montre soit impair.
   3. Supprimer v de T₂ .
7. Retourner la valeur absolue du pfaffien de la matrice d'adjacence sur (-1,0,1) de G qui est la racine carrée du déterminant.