問題タブ [minimum-spanning-tree]

最小全域木を見つけたとしましょう。ここで必要なのは、MST の A から Z へのパスだけです。これを O(n^2) 時間で行うにはどうすればよいでしょうか?

ルート A から始めます。次に、フォーム Ax (x は任意の頂点) のツリー内のすべてのエッジを調べます。

次に、AB、AC、AD などを見つけたとします。次に、それぞれについて、フォームのエッジを探します: Bx、Cx、Dx...これは明らかに O(n^2) ではありません。

では、MST を指定してパス A -> Z を見つけるためのより良い/効率的な方法は何ですか?

ありがとう

MST に新しい頂点を追加して MST を更新しようとしています。このために、私は Chin と Houck による「スパニング ツリーの更新」に従っています。 http://www.computingscience.nl/docs/vakken/al/WerkC/UpdatingSpanningTrees.pdf

論文のステップでは、2 つの特定の頂点間のパスで最大のエッジを見つける必要があります。私の考えは、頂点間のすべての可能なパスを見つけてから、パスから最大のエッジを見つけることです。これをMATLABに実装しようとしています。しかし、これまでのところ、私は成功していません。2 つの頂点間のすべてのパス、または 2 つの指定されたノード/頂点間のパスの最大のエッジさえも見つけるリード/クリア アルゴリズムは大歓迎です。

参考までに、例を挙げたいと思います。グラフに次のエッジ 1-2、1-3、2-4、および 3-4 がある場合、4 と 4 の間のパスは次のようになります。

1) 4-2-1-3-4

2) 4-3-1-2-4

ありがとうございました

私は C で Prim MST を使用しており、関数は隣接行列を取ります。もちろんの重みを考えるとA[i][j]。

これまでに見つけた最小エッジを追跡する先行配列があるとします。 predecessor[u]=v{これも最後の MST です}

ここで、現在の行列を変更し、重みを 1 に変更したいと考えていA[i][j]ます。これは、先行配列にもエッジ (インデックス) が存在していたときです。それ以外の場合は、ゼロに変更します。

どうすればいいですか？これが私の解決策です：

EXTRACT-MINオペレーションとDECREASE-KEYプライオリティ キュー内のオペレーションの関係は? これは、Prim のアルゴリズムを使用した最小スパン問題の講義で遭遇しました。

MIT の教授は、ビデオの 01:07:16 秒の時点でそれについて言及していますが、私には理解できません。誰かが私のためにこれを片付けてもらえますか?

PS: それ以外の場合は、プライオリティ キューの理解に満足しています。

最小スパニングツリーのプリムアルゴリズムに関するこのMITビデオでは、教授がπ[v] ←u71:16秒に説明しています。しかし、なぜこのステップが必要なのかわかりません。この表記 π[v] ←uは実際にはどういう意味ですか？また、次のアルゴリズムの最後の行はどういう意味ですか？ソースで提供されているアルゴリズム全体は次のとおりです。

V 個の頂点と E 個のエッジを持つグラフ G があり、G の最小スパニング ツリー T が既にわかっている場合、E からのエッジのいくつかが取得され、それらの重みがたとえば 50 だけ増加される場合、これらのエッジはある場合とない場合があります。最小スパニング ツリーに含まれます。上記のシナリオを念頭に置いて、線形時間で新しい最小スパニング ツリーを再生成する方法はありますか? 注: 重みが変更されたエッジの数は 5 つだけです。

G = (V,E)を無向グラフとします。を正w(e)の重みを持つ重み関数とします。に対する の最小T全域木をGとするw．

エッジのセットが与えられS、ここでSは のサブセットであり、が にないかのようE(G)に新しい重み付け関数Qを定義し、が にある場合。、、および集合を入力として受け取り、最小全域木 wrt を出力するアルゴリズムを設計します。時間内に実行してください。Q(e) = w(e)eSQ(e) = w(e)+100eSGTwS|S| = 10QO(V+E)

わかりました: 最初にこの質問をしてから学んだことは、MST を分割することは単一のエッジを「分割」することであり、これにより 2 つの別個のコンポーネントが作成され、各 MST は独自のコンポーネント内の頂点になります。したがって、この問題では、S のエッジが MST を小さな MST (11 ですよね?) に分割する可能性があります。あるコンポーネントを別のコンポーネントに接続する最も軽いエッジを見つけなければなりません。

私の計画は、1 つの頂点から始めて、これらのコンポーネントの 1 つ全体をカバーするまで BFS で拡張することです。コンポーネント内のすべての u について、u.color = black. 次に、戻ってコンポーネントを再度 BFS で覆います。今回は、黒く着色されていない頂点に接続するすべてのエッジを見つけ、したがってコンポーネント内に含まれず、既存のカットを横切ります。これらのエッジの反対側の頂点はキュー R に配置されます。完了したら、 Iu = RemoveMin(R)が実行されO(lgE)ます。コンポーネントをカバーするたびにのみ呼び出されるため、全体で最大 で実行されますが10*O(lgE)、それでもO(lgE)です。したがって、u を削除したら、新しいコンポーネントで BFS を実行し、そのコンポーネントですべての u.color = black を設定します。すべての黒い頂点をもう一度調べて、更新されたキーを持つすべての白い頂点を R にキューに入れることができるようにします。u = RemoveMin(R).

ですから、これは機能し、証明可能であると本当に思います。誰かが似たようなことを提案できますか?

どんなに小さな助けでも、感謝します。

こんにちは。テストの準備をしています。パートbとcを理解する必要があります。パートaが真実であり、それを証明できることはわかっていますが、パートbとcのアルゴリズムを見つけることは、現在私にはわかりません。

コストが最大のエッジがボトルネックと呼ばれる最小のボトルネックツリーについて、以下を解決します。（a）Gのすべての最小スパニングツリーはGの最小スパニングツリーですか？あなたの主張を証明してください。

（b）与えられたコストcに対して、O（n + m）時間のアルゴリズムを与えて、Gの最小ボトルネックスパニングツリーのボトルネックコストがc以下であるかどうかを調べます。

（c）Gの最小ボトルネックスパニングツリーを見つけるためのアルゴリズムを見つけます。

私を助けてくれる人に事前に感謝します

私は来週のクラステストの改訂のために私の本のすべての演習を行っています、そして私はこのサブグラフの質問について本当に混乱しています。

現在、私の考えでは、最小スパニングツリーGがすでに存在するため、その最小スパニングツリーにサブノードが存在するため、G'が存在する必要があると考えています。状態に関する限り、私は少し途方に暮れています。

グラフX'は、X'のノードセットとエッジセットがそれぞれXのノードセットとエッジセットのサブセットである場合、グラフXのサブグラフです。Gの最小全域木として（V、T）を持ち、G'=（V'、E'）をGの接続された部分グラフとします。

（a）（V'、E'∩T）がG'の最小全域木の部分グラフであることを証明します。

（b）（V'、E'∩T）はどのような条件下でG'の最小全域木ですか？あなたの主張を証明してください。

前もって感謝します！

隣接行列を使用するプリムのアルゴリズムが時間計算量をもたらす理由を誰かが私に説明できますか？O(V2)