1

これは宿題ではありません。理解するために教科書から演習をしようとしていますMST (minimum spanning tree)。

C加重無向グラフにサイクルがあるとしますG。私が理解しているように、次は正しいです：

  • の最も重いエッジはのMSTにC属していませんG。つまり、そのエッジを含むのMSTはありません。G
  • の最も明るいエッジはのMSTにC属しますG。つまり、Gそのエッジを含む の MST があります。

ここで、次の主張も正しいかどうか疑問に思います。

  • の最も明るいエッジはのすべてのMSTにC属します。つまり、そのエッジを含まない の MST はありません。GG
  • 最も重いCエッジを除くすべてのエッジは、何らかのMSTに属します。つまり、最も重いものを除く各エッジには、そのエッジを含む MST があります。C

最後の主張を証明できますか？

4

3 に答える 3

1

最初のクレームでも、最軽量のエッジが複数ある場合は、すべてを MST に含める必要はありません。

于 2012-12-15T13:25:24.577 に答える
1

あなたの主張の最初のものは常に真実です。どのグラフでも、最も明るいエッジは MST にあります。

2 つ目は常に正しいとは限りません。グラフ全体がサイクルであり、したがってすべてのノードに付随する 2 つのエッジがある場合は常に true です。ただし、一般的なケースでは、ノード間にパスがあり 、合計重みが 未満でノードを接続している場合は常に(u,v)、重みのエッジがkMST に存在することはありません。uvk

于 2012-12-15T11:49:40.113 に答える
1

あなたの主張は有効ではないと思います。問題は、より大きなグラフのサイクルのみを考慮していることです。

たとえば、サイクル内の 6 つのノードで構成されるグラフ G (ランダムな重みが >1) を考えてみましょう。あなたの主張はそのグラフに当てはまるかもしれませんが、グラフの中心にノードを 1 つ追加し、それをコスト 1 の 6 つのリンクで接続します。グラフ全体の MST は、これらの 6 つのエッジ (スターを形成する) のみで構成されます。

クレームを見ると、次のことがわかります。

  • あなたのサイクルの最も軽いエッジは MST (=星) に属していません
  • サイクルのどのエッジも MST にありません
于 2012-12-16T09:59:46.990 に答える