所以我是一名 cs 学生，我们被要求在 c 中构建一个回溯程序（没有循环，只有递归），它得到一个无向无权（无提升）图的邻接矩阵，并返回该图中完美匹配的数量否则为零。我想过使用使用 pfaffian 方向的 fkt 算法，但到目前为止我还没有弄清楚如何去做。如果您能如此友善，也许可以指导我阅读正确的书或以正确的方式看待这个问题，我将不胜感激。这是我第一次尝试回溯，我想我错过了一些关于如何实现这样的事情的基本概念。
问问题
739 次
1 回答
0
FKT 仅适用于平面图。如果你想实现它（你几乎肯定不会，因为那将是一个糟糕的作业；这是给其他发现这个问题的人的），你需要以你获得的方式对图形进行平面性测试嵌入，然后实现这些幻灯片中描述的方向算法. （草图：在原始图中找到一棵生成树并任意定位这些边。不在生成树中的边构成对偶图中的生成树。按后序访问后者树的节点；每个节点的父边（ = 原始面）访问的是最后一个方向未确定的入射边，因此如果该面当前有偶数个顺时针边，则顺时针方向，否则逆时针方向。）
于 2012-02-01T13:23:48.603 回答