15

ツリー内の最大独立セットを見つけるアルゴリズムが必要です。すべてのリーフ ノードから開始し、これらのリーフ ノードの直接の親ノードを削除してから、削除した親ノードの親ノードを選択し、ルートに到達するまでこの手順を再帰的に繰り返すことを考えています。これはO（n）時間で行われますか？どんな返信でも大歓迎です。ありがとう。

そして、ツリー内の最大支配セットを見つけるためのアルゴリズムを教えてください。

4

3 に答える 3

20

最大独立セット

ツリーの深さ優先検索により、最大独立集合を計算できます。

検索では、グラフ内の各サブツリーに対して 2 つの値が計算されます。

  1. A(i) = ノード i がセットに含まれなければならないという制約がある、i をルートとするサブツリー内の最大独立セットのサイズ。
  2. B(i) = ノード i をセットに含めてはならないという制限付きで、i をルートとするサブツリー内の最大独立セットのサイズ。

これらは、次の 2 つのケースを考慮することで再帰的に計算できます。

  1. サブツリーのルートは含まれません。

    B(i) = sum(max(A(j),B(j)) for j in children(i))

  2. サブツリーのルートが含まれます。

    A(i) = 1 + sum(B(j) for j in children(i))

ツリー全体の最大独立集合のサイズは max(A(ルート),B(ルート)) です。

最大支配セット

ウィキペディアの支配セットの定義によると、最大支配セットは常に、グラフ内のすべてのノードを含めることと自明に等しいですが、これはおそらくあなたが意味するものではありませんか?

于 2012-11-24T19:52:58.543 に答える
-2

  • 頂点の最大の独立集合を見つけるために、ツリーの重要なプロパティを使用できます。すべてのツリーは 2 部構成です。つまり、隣接する 2 つの頂点が同じ色にならないように、2 つの色だけを使用してツリーの頂点に色を付けることができます。

  • DFS トラバーサルを実行し、BLACK と WHITE で頂点の色付けを開始します。

  • より多くの頂点のセット (BLACK または WHITE) を選択します。これにより、ツリーの頂点の最大独立セットが得られます。

このアルゴリズムが機能する理由の背後にあるいくつかの直感:

  • 最初に頂点の最大独立集合の定義を再検討しましょう。エッジの端点を 1 つだけ選択する必要があり、このプロパティを満たすツリーのすべてのエッジをカバーする必要があります。エッジの両方の端点を選択することはできません。

  • では、グラフのバイカラーリングは何をするのでしょうか? 頂点のセットを 2 つのサブセット (白と黒) に単純に分割し、白の色の頂点は黒の頂点に直接接続されます。したがって、すべて白またはすべて黒のいずれかを選択すると、本質的に独立した頂点のセットが選択されます。したがって、最大独立集合を選択するには、サイズが大きい部分集合を選びます。

于 2014-05-19T04:33:59.507 に答える