アルゴリズムによるバックトラッキング。グラフ内で完璧なマッチングをカウントする

Question

私はcsの学生です。cでバックトラックプログラムを構築するように求められました。ループしない無重力（リフトなし）グラフの隣接行列を取得して返しますそのグラフ内の完全一致の数。 私はpfaffian方位を使ったfktアルゴリズムを使うことを考えましたが、これまでどのようにしているのか分かりませんでした。 あなたがとても親切で、正しい本に向かうか、この質問を見る正しい方法を教えてくれるなら、私はとても感謝しています。 私が逆戻りしようとしたのは初めてで、このようなことを実現するための基本的な考え方が不足していると思います。

Answer 1

FKTは平面のグラフのみです。あなたがそれを実装したいのであれば（、これは厄介な宿題であるので、これは他の人にも当てはまります）、planarity testにグラフが必要です埋め込みを取得し、these slidesに記載されている方向付けアルゴリズムを実装します。 （スケッチ：プライマリグラフでスパニングツリーを見つけて、それらのエッジを任意に方向付ける。スパニングツリーにないエッジは、デュアルグラフのスパニングツリーを構成する。後続のツリーのノードをポストオーダーで参照する;各ノードの親エッジ= primal face）は、向きが未定の最後の入射エッジです。そうでない場合は時計回りになります。