線形 (O(n)) 時間でツリー内の最小頂点カバーを見つける [少なくとも] 3 つのアルゴリズムがあります。私が興味を持っているのは、これらすべてのアルゴリズムを修正して、これらの最小頂点カバーの数も取得できるようにすることです。
たとえば、ツリー P4 (4 つのノードを持つパス) の場合、ノードを 1 と 3、2 と 4、または 2 と 3 から選択できるため、MVC の数は 3 です。
もちろん、3 つすべてではなく、無料のアルゴリズムのいずれかのソリューションを説明できます。私はそれらすべてに興味がありますが、追加するものがあれば、躊躇しないでください。
簡単にするために、私が知っているアルゴリズムについて説明します。
1.貪欲なアルゴリズム。
すべてのエッジに、ノードの 1 つを含める必要があることがわかります。どちらを選ぶ？「通常の」ノードとリーフを持つエッジがあるとします。どのノードを選択するのが良いですか? もちろん、葉ではありません。もう 1 つのエッジで他のノードが役立つ可能性があるからです。アルゴリズムは次のとおりです。
- 葉ではない任意のノードから開始します。
- 各子に対して DFS 呼び出しを行い、返されたときに、親または子のいずれかが頂点カバーのノードとしてマークされているかどうかを確認します。そうでない場合は、それらのいずれかを選択する必要があるため、親を選択します（そしてマークします）。
- 葉の場合は何もしません。
コードは次のとおりです: https://ideone.com/mV4bqg .
#include<stdio.h>
#include<vector>
using namespace std;
vector<int> graph[100019];
int mvc[100019];
int mvc_tree(int v)
{
mvc[v] = -1;
if(graph[v].size() == 1)
return 0;
int x = 0;
for(int i = 0; i < graph[v].size(); ++i)
if(!mvc[graph[v][i]])
{
x += mvc_tree(graph[v][i]);
if(mvc[v] < 1 && mvc[graph[v][i]] < 1)
++x,
mvc[v] = 1;
}
return x;
}
int main()
{
int t, n, a, b, i;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
for(i = 1; i <= n; ++i)
graph[i].clear();
for(i = 1; i < n; ++i)
{
scanf("%d%d", &a, &b);
graph[a].push_back(b);
graph[b].push_back(a);
mvc[i] = 0;
}
mvc[n] = 0;
if(n < 3)
{
puts("1");
continue;
}
for(i = 1; i <= n; ++i)
if(graph[i].size() > 1)
break;
printf("%d\n", mvc_tree(i));
}
return 0;
}
2. 動的計画法アルゴリズム。
再帰を使用してタスクを解決することもできます。
MVC(v) = min(
1 + sum(MVC(child) for child in v.children),
v.children.size + sum(MVC(grandchild) for grandchild in v.grandchildren)
)
ノード v にいるときは、MVC かどうかのどちらかです。そうである場合、それを結果 1 (v を含むため) に追加し、すべての v の子のサブツリーのサブ結果を追加します。一方、それが MVC にない場合、彼のすべての子は MVC にある必要があるため、子の結果数に追加し、子のそれぞれについて、子のサブ結果を追加します (つまり、v の孫)。親と祖父母について、各ノードを 2 回チェックするため、アルゴリズムは線形です。
3. 動的計画法その 2。
ノード v の 2 つの状態 (1 - MVC 内、2 - MVC 内ではない) の代わりに、「たぶん MVC 内」を 3 つ追加することができます。それはどのように役立ちますか？最初に、v が MVC に含まれているかどうかがわからないため、MVC(v = ランダム ノード、「たぶん」) を呼び出します。「たぶん」の結果は、「はい」と「いいえ」の結果の最小値です。「はい」の結果は 1+sum(MVC(child, "maybe") for child in v.children) です。そして、「いいえ」の結果は sum(MVC(child, "yes") for child in v.children) です。その理由はかなり明確だと思います。そうでない場合は、コメントで質問してください。したがって、式は次のとおりです。
MVC(v, "maybe") = min(MVC(v, "yes"), MVC(v, "no"))
MVC(v, "yes") = 1 + sum(MVC(child, "maybe") for child in v.children)
MVC(v, "no") = sum(MVC(child, "yes") for child in v.children)
すべてのノードが「はい」と「いいえ」の 2 回チェックされるため、複雑さも O(n) になります。