2

開始ノードと終了ノードを持つ有向グラフで、開始ノードから終了ノードまでのすべての可能なパスに少なくとも 1 つのメンバーが含まれるようなノードの小さな (最小である必要はない) セット S を見つける方法S を設定します。グラフにはループがある場合があることに注意してください。これはNP困難かもしれないことを知っています。

  1. グラフからそのような S を 1 つまたは複数見つける近似方法はありますか?

  2. または、集合 S が与えられた場合、S が解であることをどのように確認できますか? (グラフのループにより、検証が非常に複雑になるようです。)

ありがとう。

PS: この質問は、最小 k パス頂点カバーの問題に似ています。

4

1 に答える 1

1

（2）の場合、グラフから問題のノードをすべて削除し、s / tパスがまだ存在するかどうかを確認することで、セットにこのプロパティがあることを簡単に確認できます。もしそうなら、あなたのセットのノードのどれも含まなかったいくつかのパスがあったに違いありません。そうでない場合は、すべてのパスにセットのノードが少なくとも1つ含まれている必要があります。

（1）についてはよくわかりませんが。

お役に立てれば！

于 2012-05-23T20:08:08.793 に答える