theory - どの MST にも含まれないエッジ

Question

これは宿題の質問です。私は解決策を望んでいません - 私は考えていた解決策を提供していて、それが良いのか、それともなぜ問題なのかを知りたいと思っています.

私の動機は、重み付けされていない無向グラフのどのエッジが MST の一部ではないかを見つけることです。この問題は、複数のエッジが同じ値を持つ場合にのみ意味があります。それ以外の場合、MST は一意です。

私のアイデアは、プリムのアルゴリズムにわずかな変更を加えたものです。すべてのステップで最小エッジを S から T に追加するのではなく (ここで、S と T は頂点の 2 つのセットです)、代わりに最小エッジと同じ値のより多くのエッジを探します。 S から最小エッジが向かう頂点に向かいます。そうすることで、MST に現れるすべてのエッジを含むグラフを受け取ることができると思います。これが正しければ、エッジ リストと元のグラフ エッジ リストを XOR するだけで、どの MST にもないエッジを見つけることができます。

前もって感謝します。

Answer 1

見つかったすべてのエッジ (=重みが等しいもの) を追加しますか? その場合、いくつかのエッジが失われます。

辺のコストが等しい五角形を考えてみましょう。1 つのノードから開始し、2 つのエッジを隣接する 2 つのノードに追加します。次のステップでは、これらの 2 つの隣接するノードから 2 つの切断されたノードに向かう 2 つのエッジを追加すると、完了です。ただし、すべてのエッジのコストは等しく、MST に存在することはすべて有効です。最後の 2 つのノード間のエッジはアルゴリズムに含まれませんが、MST の一部である可能性があります。

それはさらに悪いです。最後のエッジのコストが低いとします。アルゴリズムにはまだ含まれていませんが、すべての MST に存在します。すべての可能性を考慮して、ステップごとにいくつかのエッジを追加していますが、これらのエッジを追加すると、次のステップが変わります。