65

Kruskal の最小スパニング ツリーのアルゴリズムの逆は機能しますか? つまり、すべてのステップで最大の重み (エッジ) を選択するということですか?

最大スパニングツリーを見つけるための他のアイデアはありますか?

4

8 に答える 8

77

はい、そうです。

Kruskal によるネットワーク G の最大重みスパニング ツリーを計算する 1 つの方法は、次のように要約できます。

  1. G のエッジを重みの降順に並べ替えます。最大重みスパニング ツリーを構成するエッジのセットを T とします。T = ∅ に設定します。
  2. 最初のエッジを T に追加します。
  3. T でサイクルを形成しない場合にのみ、次のエッジを T に追加します。残りのエッジがない場合は、G が切断されたことを報告します。
  4. T に n-1 個のエッジがある場合 (n は G の頂点の数)、停止して T を出力します。それ以外の場合は、ステップ 3 に進みます。

ソース: https://web.archive.org/web/20141114045919/http://www.stats.ox.ac.uk/~konis/Rcourse/exercise1.pdf .

于 2011-02-14T13:35:32.760 に答える
44

Wolfram MathWorld の最大スパニング ツリーから:

「最大スパニング ツリーは、最大の重みを持つ重み付きグラフのスパニング ツリーです。各エッジの重みを否定し、クルスカルのアルゴリズムを適用することで計算できます( Pemmaraju and Skiena, 2003, p. 336)」。

于 2011-02-14T13:29:46.073 に答える
6

すべてのエッジの重みを反転して最小化すると、最大スパニング ツリーが得られますか? それが機能する場合は、同じアルゴリズムを使用できます。もちろん、ゼロウェイトは問題になります。

于 2011-02-14T13:28:24.467 に答える
1

元のグラフの重みを否定し、否定されたグラフで最小全域木を計算すると、正しい答えが得られます。理由は次のとおりです。両方のグラフの同じスパニング ツリーの場合、一方のグラフの加重和は他方のグラフの否定になります。したがって、否定されたグラフの最小スパニング ツリーは、元のグラフの最大スパニング ツリーを与える必要があります。

于 2012-12-24T04:36:01.360 に答える