graph - Primのアルゴリズムで得られたグラフの最小全域木

Question

Prim のアルゴリズムの問​​題について支援が必要です。

Prim のアルゴリズムによって得られたグラフ G の最小全域木を T とする。G に新しい頂点と重み付きのいくつかの辺を追加し、新しい頂点を G のいくつかの頂点に接続して得られるグラフを Gnew とします。新しい辺の 1 つを T に追加することで、Gnew の最小全域木を構成できますか? はいと答えた場合は、その方法を説明してください。いいえの場合は、その理由を説明してください。

前もって感謝します！！

Answer 1

新しいエッジの 1 つを T に追加することで、Gnew の最小全域木を構築できますか?

いいえ、一般的ではありません。T頂点を順番に考えて生成されたと仮定するv1,v2,...,vn-1

vnを新しい頂点とし(v1,vn)、重み付きエッジ (v1 は T のルート) とします。 の重みが T(v1,vn)の の重みよりも小さい場合(v1,v2)、これは MST ではなくなります。

Answer 2

すべての場合で T に新しいエッジを追加できるわけではありません。新しいエッジの重みに依存します。新しいエッジの重みがグラフの他の重みよりも小さい場合、古い MST(T) が変更されることがあるためです。