最小スパニングツリーは、サイクルプロパティで指定されたエッジだけを持たないでしょうか。[重複]

Question

この質問はすでにここで答えを持っています

どのようなエッジがいずれにもないのですか？ （1回）

閉じた 4月前>。

Answer 1

$ g $ のEdge $ E $ であると言ってください。 / strong> $ g $ にサイクルが存在する場合は、 $ e $ には最大の重みがあります。

define $ {\ cal b}={e~ |〜e $ は $ g \} $ すべての悪いエッジのコレクションです。

あなたの質問は、グラフ $（g - {\ cal b}）$ $ g $です。 （すべてのエッジウェイトが異なると仮定して）答えはyes！

です

これを証明するには、 $（g - {\ cal b}）$ が非巡回です。

$（g - {\ cal b}）$ には、 $ c $が含まれています。 。 $ c $ は、 $ g $ のサイクルです。 $ e ^ * $ を、サイクル $ c $ の最大重みのエッジになります。 $ e ^ * $ は悪いエッジですので、それはグラフであるべきではありません> $（g - {\ cal b}）$ が最初の場所です。これは、 $（g - {\ cal b}）$ が非巡回です。

Answer 2

あなたの質問を理解していなかったらすみません、私が尋ねることを意味するのかどうかは、このエッジがサイクルにない場合はエッジがMSTにならないように可能であるかどうかです。

これが私の答えです。

グラフGにエッジ（u、v）があると仮定して、サイクルの一部ではありません。これは、uからvへのパスがないことを意味します（u、v）。 エッジ（u、v）がMSTにいなかった場合、これはこのMSTのUからVへのパスがないことを意味すると、MSTは切断され、したがってまったくMSTではありません。 したがって、エッジがサイクルの一部ではない場合は、グラフのMSTになければなりません。