問題タブ [minimum-spanning-tree]

ダイクストラは通常、グラフ内の 2 つのノード間の最短距離を見つけるために使用されます。最小全域木を見つけるために使用できますか? もしそうなら、どのように？

編集: これは宿題ではありませんが、古い模擬試験の問題を理解しようとしています。

私はコーメンらの本から勉強してきましたが、彼らが提供したアルゴリズムについて少し混乱しています。Prim のアルゴリズムの概念がウィキペディアでどのように機能するかを理解しましたが、私の本で提供されているアルゴリズムを使用してその動作を模倣することはできません。

章の次のオンライン コピーを参照して ください。

アルゴは上記リンクの 13 ページに記載されており、図の例は前のページにあります。

ここで、最初のステップで、例のケースでアルゴリズムを使用します。

u <--- ExtractMin(Q) を介したノード A。次に、図のように、Adj[u] にノード b とノード h の 2 つのエントリがあります。

最初に v <---- ノード b を設定します。次に、v が Q に属しているかどうかを確認します。そうです。w(u,v) < key[v] かどうかを確認します。真実。したがって、PI[v] <--- u およびキー [v] <--- w(u, v) です。こんなに取れました。これは 12 ページの図の (b) に示されています。

しかし、アルゴリズムは「Adj[u]の各vに対して」と言います。

したがって、次のステップでは v <--- ノード h を設定する必要があります。次に、v が Q に属しているかどうかを確認します。そうです! w(u,v) < key[v] ですか? です！key[v] = 無限だから! しかし、この図では (c) の部分で別のステップが示されています。

あああああ！なんで？

(任意の) 接続された無向グラフ G があり、そのエッジが異なる重みを持つ場合、

1. G のすべての MST には最小の加重エッジが含まれていますか?
2. 最大加重エッジを含まない G の MST はありますか?

また、このような MST の質問に対処する際に心に留めておく必要がある重要な事柄について、誰かがヒントを与えることができれば、さらに感謝しています。

これは宿題の問題です。ありがとう。

私は大学で次の問題を提示されました：

G =（V、E）を、エッジe∈Eでコストc _e > = 0の（無向）グラフとします。Gで最小コストの全域木Tが与えられていると仮定します。ここで、新しいエッジがGに追加され、2つのノードv、tv∈Vをコストcで接続する_とします。

1. Tが最小コストのスパニングツリーであり、新しいエッジがGに追加されているかどうかをテストするための効率的なアルゴリズムを提供します（ただし、ツリーTには追加されません）。アルゴリズムを時間O（| E |）で実行します。O（| V |）時間でできますか？ツリーTとグラフGを表すためにどのデータ構造が使用されるかについての仮定に注意してください。
2. Tが最小コストのスパニングツリーではなくなったとします。線形時間アルゴリズム（時間O（| E |））を与えて、ツリーTを新しい最小コストスパニングツリーに更新します。

これは私が見つけた解決策です：

動作しているように見えますが、問題がO（| E |）時間であるのに対し、O（| V |）時間でこれを簡単に実行できます。私は何かが足りないのですか？

ちなみに私たちは誰にでも助けを求めることが許可されているので私は浮気していません：D

重み付きエッジを持つ有向グラフが与えられた場合、最小の重みを持つサブグラフを与えるためにどのアルゴリズムを使用できますが、グラフ内の任意の頂点から他の頂点への移動が可能です（任意の2つの頂点間のパスが常に存在するという仮定の下で） 。

そのようなアルゴリズムは存在しますか？

無向加重グラフのすべての最小スパニングツリー（MST）を見つける実装（networkxライブラリを使用しています）を探していました。

クラスカルのアルゴリズムとプリムのアルゴリズムの実装しか見つかりません。どちらも単一のMSTしか返しません。

この問題に対処する論文（カウントと生成へのアプリケーションですべての最小スパニングツリーを表すなど）を見たことがありますが、コードに変換する方法を考えようとすると、頭が爆発する傾向があります。

実際、私はどの言語の実装も見つけることができませんでした！

先生からその問題の動的計画法の解決策を教えてもらいましたが、グーグルで見つけられなかったので存在しないと思います。

とにかく、グラフとak、たとえば3が与えられた場合、そこから3つの最良のMSTを見つける必要があります。グラフがk個のサブツリーを持たないようなものである場合、同じツリーを複数回返すか、次善のツリーを返すことができます。

私はそれに対する解決策を本当に考えることができません。

私は、最小全域木の切断特性に関するオンライン プレゼンテーションや教科書を読むことに多くの時間を費やしてきました。何を説明しようとしているのか、あるいはなぜそれが実用的なのかさえ、私にはよくわかりません。おそらく、MST に追加するエッジを決定するのに役立つと思われますが、それがどのように達成されるかはわかりません。これまでのところ、カット プロパティについての私の理解では、MST を 2 つの任意のサブセットに分割するということです。ここで何か助けはありますか？ありがとう！

スパニングツリーの計算に3種類の制限があるとします。

1. 制約の程度（例：スパニングツリー内のノードは、他の3つのノードまでしか接続できません）
2. 境界の直径（例：すべてのエッジの重みを合計すると、100を超えることはできません）。
   2.1。可能であれば、この基準を満たすすべてのサブツリーを表示します。
3. 両方

これを解決するために、私を狂わせない優れたアルゴリズムはありますか？これをかなり大きな入力（1000以上のノード）で実行する必要があるので、複雑さも高くなりすぎないようにします。

ウィキペディアより。セットに参加しているので、外側のループはlogVであることを理解しています。しかし、内部ループが発生します。

セットを追跡するために同値関係を使用する場合、それはセットを表す要素のみを取得していることを意味するため、すべての要素を持っているわけではないため、2 つのセット間で最小の重みを持つエッジを決定することはできません。 . 子への参照を保持するように構造を変更する場合でも、各セットのすべての子を取得する必要があります。つまり、最悪のシナリオ、各セットの O(V/2) = O(V) です。

その後、2 つのコンポーネントを接続する最小のエッジを見つける必要があります。これは、2 つのコンポーネントを接続するすべてのエッジを調べることを意味します。したがって、各ノードを反復処理して、そのエッジが他のコンポーネントの要素に接続されているかどうかを確認する必要があります。接続している場合は、現在の最小エッジよりも小さいかどうかを確認します。

つまり、ノードを反復する外側のループと、そのノードのエッジを反復する内側のループ - O(V E)。O(logV) ループ内にあるため、O(logV V*E) が得られます。

さて、すべてのエッジを繰り返し処理する必要があるように思えますが、2 つのコンポーネント間の最小エッジをどのように選択するのでしょうか? 特定のエッジが異なるコンポーネントのノードを接続しているかどうかはわかりますが、それらを接続しているノードの重みが最小かどうかはわかりません。そして、最小の重量のものを取得すると、それらが接続されない可能性があります.