20

木の最小頂点カバーを取得するための適切なアルゴリズムは何ですか?

入力：

ノードのネイバー。

出力：

頂点の最小数。

4

7 に答える 7

15

ここの回答を読んでもよくわからなかったので、ここから投稿しようと思いました

一般的な考え方は、任意のノードでツリーをルートし、そのルートがカバー内にあるかどうかを確認することです。そうである場合は、再帰によって、その子をルートとするサブツリーの最小頂点カバーを計算します。そうでない場合は、ルートとその子の間のすべてのエッジがカバーされるように、ルートのすべての子が頂点カバー内にある必要があります。この場合、ルートの孫に対して再帰します。

たとえば、次のツリーがあるとします。

    A
   / \
  B   C
 / \ / \
D  E F  G

調べると、最小頂点カバーが であることがわかります{B, C}。この最小カバーを見つけます。

ここでは から始めAます。

Aは表紙です

と の 2 つのサブツリーに移動し、BこのCアルゴリズムを再帰します。カバーされていたとしても、カバーに含まれる必要があるかどうかについては何も言えBません。CABACBC

(ルートとその子の 1 つが最小カバー ( ) にある次のツリーについて考えてください{A, D})

  A
 /|\___
B C    D
      /|\
     E F G

)

Aは表紙にありません

ABしかし、 andをカバーする必要があることはわかっているので、カバーにandACを追加する必要があります。andはカバーに含まれているため、 andを再帰する代わりに、その子を再帰できます(実行したとしても、それ以上の情報は得られません)。BCBCBC

「正式に」

をルートとする最小C(x)カバーのサイズとしxます。

それで、

C(x) = min ( 
            1 + sum ( C(i) for i in x's children ),                    // root in cover
            len(x's children) + sum( C(i) for i in x's grandchildren)  // root not in cover
            )
于 2012-11-13T23:34:13.430 に答える
11

T(V,E) はツリーです。これは、任意の葉について、最小頂点被覆には葉または葉に隣接する頂点のいずれかを含める必要があることを意味します。これにより、頂点カバー S を見つけるための次のアルゴリズムが得られます。

  1. ツリー内のツリー (BFS または DFS)、O(|V|) のすべての葉を検索します。
  2. (u,v) がエッジで v が葉である場合、u を頂点カバーに追加し、(u,v) を削除します。これにより、フォレスト T_1(V_1,E_1),...,T_n(U_n,V_n) が残ります。
  3. ここで、V_i={v}、つまり |V_i|=1 の場合、v に含まれるすべてのエッジがカバーされるため、そのツリーを削除できます。これは、頂点が 1 つまたはまったくない再帰の終了条件があることを意味し、S_i を各 T_i の被覆として計算し、ステップ 2 のすべての頂点が各 T_i の被覆を結合するものとして S を定義できます。

あとは、元の木に頂点が 1 つしかない場合は 1 を返し、再帰を開始せず、最小の頂点カバーを計算できることを確認するだけです。

編集：

実際、少し考えてみれば、単純な DFS バリアントで実現できます。

于 2009-06-01T14:17:46.687 に答える
10

ここで、あなたの質問に対するより関連性の高い回答を見つけていただければ幸いです。

私は自分のソリューションについて考えていましたが、おそらくそれを磨く必要がありますが、動的プログラミングがタグの1つにある限り、おそらく次のことが必要です:

  1. 各 u 頂点に対して、S+(u) は頂点 u を含むカバー サイズであり、S-(u) は頂点 u を含まないカバー サイズです。
  2. S+(u)= 1 + Sum(S-(v)) u の子 v ごと。
  3. S-(u)=Sum(max{S-(v),S+(v)}) u の子 v ごと。
  4. 答えは max(S+(r), S-(r)) で、r はツリーのルートです。

これを読んだ後。ウィキの記事に記載されているため、最大の独立したセットを見つけるために上記のアルゴリズムを変更しました

セットは、その補数が頂点カバーである場合にのみ独立しています。

したがって、最小値を最大値に変更することで最大の独立集合を見つけ、最小の頂点カバーを補うことができます。これは、両方の問題が同等であるためです。

于 2009-05-29T17:09:10.253 に答える
2 
{- Haskell implementation of Artem's algorithm -}

data Tree = Branch [Tree]
    deriving Show

{- first int is the min cover; second int is the min cover that includes the root -}
minVC :: Tree -> (Int, Int)
minVC (Branch subtrees) = let
    costs = map minVC subtrees
    minWithRoot = 1 + sum (map fst costs) in
    (min minWithRoot (sum (map snd costs)), minWithRoot)
于 2009-05-30T17:17:13.443 に答える
2

DFS ベースのアルゴリズムを使用して、この問題を解決できます。

DFS(node x)
{

    discovered[x] = true;

    /* Scan the Adjacency list for the node x*/
    while((y = getNextAdj() != NULL)
    {

        if(discovered[y] == false)
        {

            DFS(y);

           /* y is the child of node x*/
           /* If child is not selected as a vertex for minimum selected cover
            then select the parent */ 
           if(y->isSelected == false)
           {
               x->isSelected = true;
           }
        }
   }
}

リーフ ノードが頂点カバーに選択されることはありません。

于 2014-05-18T06:21:15.227 に答える
0

単純に線形プログラムを使用して、最小頂点被覆問題を解決します。整数線形プログラムとしての定式化は、次のようになります: ILP の定式化

あなた自身の実装がこれらの高度に最適化された LP ソルバーよりも高速になるとは思いません。

于 2014-05-17T10:56:27.023 に答える