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).
ですから、これは機能し、証明可能であると本当に思います。誰かが似たようなことを提案できますか?
どんなに小さな助けでも、感謝します。