だから私はcsの学生であり、無向の重み付けされていない（リフトなし）グラフの隣接行列を取得し、そのグラフの完全一致の数を返すc（ループなし再帰のみ）でバックトラッキングプログラムを構築するように依頼されましたそれ以外の場合はゼロ。pfaffian方向を使用するfktアルゴリズムを使用することを考えましたが、これまでのところ、その方法がわかりません。あなたがとても親切で、この質問を正しい本や正しい見方に導いてくれるなら、私はとても感謝しています。私がバックトラックを試みたのは初めてであり、そのようなことをどのように実装するかについてのいくつかの基本的な概念が欠けていると思います。
1 に答える
0
FKT は平面グラフ専用です。それを実装したい場合 (そして、それはお粗末な宿題になるので、ほぼ確実に実装しません。これは、この質問を見つけた他の人のためのものです)、次のような方法でグラフの平面性をテストする必要があります。埋め込み、次にこれらのスライドで説明されている向きアルゴリズムを実装します. (スケッチ: プライマル グラフでスパニング ツリーを見つけ、それらのエッジを任意に方向付けます。スパニング ツリーにないエッジは、デュアル グラフのスパニング ツリーを構成します。後者のツリーのノードを後から順に調べます。各ノードの親エッジ ( = primal face) 訪問したのは、方向が未定の最後の入射エッジです。そのため、面に現在時計回りのエッジが偶数個ある場合は時計回りに、そうでない場合は反時計回りに方向付けます。)
于 2012-02-01T13:23:48.603 に答える