問題タブ [minimum-spanning-tree]

消費税はこちら

与えられたグラフ G (n 個の頂点と m 個の辺を持つ) の最小全域木 T と、G に追加する重み w の新しい辺 e = (u, v) が与えられたとします。グラフ G + e の最小全域木。完全なクレジットを受け取るには、アルゴリズムを O(n) 時間で実行する必要があります。

私はこの考えを持っています：

In the MST, just find out the path between u and v. Then find the edge (along the path) with maximum weight; if the maximum weight is bigger than w, then remove that edge from the MST and add the new edge to the MST.

トリッキーな部分は、O(n) 時間でこれを行う方法です。

問題は、MST の保存方法です。通常の Prim のアルゴリズムでは、MST は親配列として格納されます。つまり、各要素は対応する頂点の親です。

物品税が MST を示す親配列を私に与えると仮定すると、どうすれば上記のアルゴリズムを O(n) で解放できますか?

まず、親配列から u と v の間のパスを特定するにはどうすればよいですか? u と v の 2 つの祖先配列を使用して、共通の祖先をチェックすると、パスを取得できますが、逆になります。この部分で、共通の祖先を見つけるには、少なくとも O(n^2) で行う必要があると思いますよね?

次に、パスがあります。しかし、パスに沿った各エッジの重みを見つける必要があります。グラフは Prim のアルゴリズムに adjacency-list を使用すると思われるので、O(m) (m はエッジの数) を実行して、エッジの各重みを特定する必要があります。

...

したがって、O（n）でアルゴリズムを実行できるとは思いません。私が間違っている？

これは、ほとんどのグラフ アルゴリズムが負の数に簡単に適応しないのはなぜですか?のフォローアップの質問です。.

最短パス (SP) は、パスに沿ってすべての重みを合計し、最小のものを見つけようとするため、負の重みに問題があると思います。

しかし、最小スパニング ツリー (MST) が負の重みの問題を抱えているとは思いません。なぜなら、全体の重みの合計を気にせずに、単一の最小重みエッジを取るだけだからです。

私は正しいですか？

ここに物品税があります：

重み付き連結グラフGからエッジの最小重み連結サブセットTを見つける問題を考えてみましょう。Tの重みはTのすべてのエッジ重みの合計です。最小重み連結サブセットTを計算するための効率的なアルゴリズムを提供します。

これが私が持っているものです：

1. 重みが正と負の両方で混合されていると仮定する必要があります。この物品税には、両方の種類の重量の組み合わせのみが意味をなします。

2. 最初にエッジを並べ替えるので、負のエッジが最初に来ます。

3. クラスカルのアルゴリズムを利用することを検討しますが、いくつかの変更を加える必要があります

4. ネガティブエッジを歓迎するので、できるだけ多くのネガティブエッジを追加しようと思います。

5. さらに、すべての負のエッジが接続されていない場合に備えて、いくつかの正のエッジを追加することができ、ブリッジとしていくつかの正のエッジが必要になる場合があります。

わかりました、上記は私の考えです。でも手を汚そうとすると行き詰まってしまいます。

可能な最小ウェイトセットを常に記録するにはどうすればよいですか？

例えば、

{0、1}の重みは-20です

{2、3}は重み-10です

{1、3}の重みが11の場合、もちろん{1、3}は必要ありません。

または、{1、3}の重みが9の場合、

どのようなデータ構造で、常に最小の重みとその重みの頂点を維持できますか？

この物品税が目的とするサブセットであることに注意する価値がありedgesます。

重み付き連結グラフGからエッジの最小重み連結サブセットTを見つける問題を考えてみましょう。

これは、すべての頂点を含める必要があることを意味します。

また、それはMST以上のものです。頂点に2つのエッジがある場合、1つは-1で、もう1つは-2であると考えてください。通常のMSTアルゴリズムでは、-2のエッジのみが取得されます。ただし、この物品税では、全体の重量をさらに減らすために、-1と-2の両方を使用する必要があります。

I am making a program to compute minimum cost routes, using minimal spanning trees. I did my implementation in c + + but I could not make a graphical interface to read the input file, so I decided to pass it to Java language and create the interface using Netbeans. Herés my code in c++:

ここに演習があります：

以下を証明するか、反例を挙げてください。

(a) 無向グラフの最小全域木における頂点のペア間のパスは、必ずしも最短 (最小重み) パスですか?

(b) グラフの最小全域木が一意であるとします。無向グラフの最小全域木における頂点のペア間のパスは、必ずしも最短 (最小重み) パスですか?

私の答えは

(a)

いいえ、たとえば、グラフ 0、1、2、0-1 は 4、1-2 は 2、2-0 は 5、0-2 の真の最短パスは 5 ですが、mst は 0-1-2 です。 、mst で、0-2 は 6

(ロ)

私の問題はこれにあります（b）。

whether the MST is unique最短経路にどのように影響するかわかりません。

まず、私の理解では、エッジの重みが明確でない場合、複数の MST が同時に存在する可能性がありますよね?

第 2 に、MST が一意であっても、上記の (a) の答えは (b) にも当てはまりますよね?

特定のエッジ (u,v) を含める必要があるように、最小スパニング ツリーのクラスカルのアルゴリズムを変更する方法を考えられる人はいますか?

重みのある無向連結グラフが与えられます。w:E->{1,2,3,4,5,6,7} - 可能な重みは 7 つしかないことを意味します。O(n+m) の Prim のアルゴリズムと O( m*a(m,n)) の Kruskal のアルゴリズムを使用してスパニング ツリーを見つける必要があります。

これを行う方法がわかりません。ここでウェイトがどのように役立つかについてのガイダンスが本当に必要です.

加重グラフ G を取り、G の最小スパニング ツリーの変化を引き起こす非 MST エッジへのコストの最小の変化を見つけるアルゴリズムを考案します。

これまでの私の解決策（提案が必要）：

MST に変更を加えるには、非 MST エッジ st の重みを変更する必要があります。これは、MST の開始頂点と終了頂点のパスの最大エッジよりも 1 小さくなります。

したがって、MST のエッジをウォークすることから始めて、頂点ごとに非 MST エッジがあるかどうかを確認します。存在する場合、(MST 内の) エッジの終点に到達するための bfs を実行できます。非 MST エッジの重みは、パス内の最大エッジの重みよりも 1 小さい値に更新する必要があります。

これにより、非 MST エッジが MST に含まれ、以前の最大エッジが MST から削除されます。

この解決策が正しいかどうか誰かがわかりますか? ありがとう。

E を指定された有向辺セットとします。E のエッジが、すべてのノード (ルート ノードを除く) が 1 次数しか持たない有向木 T を形成できることがわかっているとします。問題は、T 内のすべてのパスを見つけるために、エッジ セット E を効率的にトラバースする方法です。

たとえば、有向辺セット E={(1,2),(1,5),(5,6),(1,4),(2,3)} があるとします。このような集合 E は、次数が 1 つだけの有向木 T を生成できることがわかっています (ルート ノードを除く)。次のようにすべてのパスを見つけるために、エッジセット E をトラバースする高速な方法はありますか?

ところで、E の辺の数が |E| だとすると、すべてのパスを見つけるには複雑さが必要ですか?

スパニングツリーとカットは密接に関連していることはすでに見てきました。これが別の接続です。クラスカルのアルゴリズムがスパニングツリーに追加する最後のエッジを削除しましょう。これにより、ツリーが2つのコンポーネントに分割され、グラフにカット（S、S）が定義されます。このカットについて何が言えますか？使用しているグラフが重み付けされておらず、クラスカルのアルゴリズムがそれらを処理するために、そのエッジがランダムに均一に順序付けられていると仮定します。ここに注目すべき事実があります。少なくとも1/n ^ 2の確率で、（S、S）はグラフの最小カットであり、カットのサイズ（S、S）はSとSの間で交差するエッジの数です。これは、プロセスをO（n ^ 2）回繰り返し、見つかった最小カットを出力すると、Gの最小カットが高い確率で生成されることを意味します。重み付けされていない最小カットのO（mn ^ 2 log n）アルゴリズムです。

• これは、クラスカルのアルゴリズムを使用してグラフを処理するためのn ^ 2のユニークな方法があるという事実に依存しませんか？つまり、クラスカルのアルゴリズムが10ノードのグラフを処理するための3つの固有の方法しかない場合、この処理をn ^ 2回繰り返しても、n^2の固有の「最後のエッジ」は生成されません。一意の最終カットがn^2未満（つまり、一意の「最後のエッジ」がn ^ 2未満）のシナリオでは、どのように機能しますか？

• 合計でn^2未満のエッジがある場合はどうなりますか？たとえば、9つのエッジしかない10個のノードの連結グラフを作成できます。つまり、アルゴリズムを何度繰り返しても、n^2個の一意の「最後のエッジ」はありません。この状況でどのように機能しますか？

• すべてのエッジをループして、エッジが最小カットであるかどうかを確認する方が簡単ではないでしょうか。nノードのグラフでは、一意のエッジの最大数はn + n-1 + n-2 ... + 1エッジであり、n^2未満です。また、n^2がn^2 log n未満であることを考慮すると、これが高速であるため、すべてのエッジをループするだけではどうでしょうか。