1

私が与えられたヒューリスティックな解決策は次のとおりです。

  • グラフで深さ優先検索を実行する
  • 葉をすべて削除する
  • 残りのグラフは頂点カバーを形成します

「このヒューリスティックが、頂点カバーの最適解の最大 2 倍の大きさであることを示してください」という質問が与えられました。どうすればこれを表示できますか?

4

2 に答える 2

0

グラフが接続されていると仮定します (接続されていない場合は、この問題をコンポーネントごとに個別に解決できます)。

また、dfs-tree は根付きであり、葉は根付きの dfs-tree に子を持たない頂点であると仮定します (これは重要です。別の方法で定義すると、アルゴリズムが機能しない可能性があります)。

私たちは物事に示す必要があります:

  1. アルゴリズムによって返される頂点のセットは、頂点カバーです。実際、任意の無向グラフの dfs-tree には、次のタイプのエッジしか存在できません: ツリー エッジ (そのようなエッジは、少なくともそのエンドポイントの 1 つがリーフではないためカバーされます) とバック エッジ (再び、そのエンドポイントの 1 つ)バック エッジは頂点からその先祖に向かうため、 は葉ではありません (葉は葉の先祖になることはできません)。

  2. dfs-tree について考えてみましょう。残りのエッジは無視してください。非葉頂点の半分以下を使用して木の端をカバーすることは不可能であることを示します。S を最小頂点カバーとする。葉ではなく、v含まれていない(つまり、問題のヒューリスティックによって返されたが、最適な答えには含まれていない)頂点を考えてみましょう。はリーフではないため、dfs ツリーにエッジがあります (は の後継です)。エッジは で覆われています。したがって、です。as ( whereおよび_vvSvvv -> uuvv -> uSuSfSf(v) = uvu前の文と同じ意味です）。は dfs-tree のv親であることに注意してください。uただし、ツリー内の頂点の親は 1 つだけです。したがって、f注射です。これは、ヒューリスティックによって返された集合内の頂点の数が、最適な答えのサイズを超えていないことを意味します。それがまさに私たちが示す必要があったものです。

于 2016-10-25T13:00:32.107 に答える
0

悪いニュース: ヒューリスティックは機能しません。厳密に言えば、1 つの孤立した頂点は質問の反例です。それにもかかわらず、ヒューリスティックは、孤立した頂点と 2 点クリークに対して修正したとしても、頂点カバー ソリューションをまったく提供しません。頂点数が 1 から 3 の全結合グラフを見てみましょう。

1 - 厳密に言うと、孤立した頂点は葉ではありません (葉は次数 0 ですが、葉は次数 1 の頂点です)。したがって、ヒューリスティックはそれを保持しますが、頂点カバーは保持しません。

2 - ヒューリスティックは両方の葉をドロップしますが、頂点カバーはそれらの少なくとも 1 つを保持します

3 - ヒューリスティックは 1 つの頂点を残しますが、頂点カバーはこのクリークの少なくとも 2 つの頂点を保持する必要があります

于 2016-10-25T12:23:41.323 に答える