算法回溯。在圖中計算完美匹配

Question

所以我是一個cs的學生，我們被要求在c（沒有循環遞歸）中構建一個回溯程序，它得到一個無向（無升降）圖的鄰接矩陣，並返回該圖中完美匹配的數量，否則爲零。 我想過使用fkt算法，它使用pfaffian方向，但到目前爲止我還沒有想出如何這樣做。 如果你可以如此友善，也許指導我到正確的書或正確的方式來看看這個問題，我將非常感激。 這是我第一次嘗試回溯，我想我錯過了一些如何實現這樣的事情的基本概念。

Answer 1

FKT僅適用於平面圖表。如果你想實現它（和你幾乎肯定不會，因爲這將是一個糟糕的功課;這是其他人誰發現這個問題），你需要planarity test圖表以這種方式，你獲取嵌入，然後實現these slides中描述的方向算法。 （示意圖：在原始圖中找到一棵生成樹，並任意定位這些邊，生成樹中不包含的邊包含對偶樹中的一棵生成樹，訪問後一棵樹的節點;每個節點的父邊（ =原始面）訪問是方向未定的最後一個事件邊緣，因此如果面部當前具有偶數個順時針邊緣，則順時針方向，否則逆時針方向）。