MST がツリーであるかどうかを理解するのに苦労しています。
グラフ G = (V, E) が与えられた場合、V 内のすべての頂点を接続し、最小の総重みを持つエッジ T ⊆ E の任意のサブセットを行うとします。負の重みがあります。- すべてのエッジに正の重みがあります。
負の重みを持つ可能性のあるエッジの場合、それはツリーである必要があり、すべてのエッジが正の重みを持つエッジの場合、他のサブグラフである可能性があると考えています。
私が正しいか間違っているかを助けてください。
それが木でなければならない場合、接続性と最小性に対する矛盾を説明していただけますか? しかし、それが他のサブグラフである可能性があると思われる場合は、ツリーではない可能性のある接続されたグラフの重みが低い例を示していただけますか。
負の重みがある場合、最小スパンサブグラフがツリーであることを保証できません。すべてのエッジの重みが -1 である 3 つの頂点の完全なグラフを考えてみましょう。
編集あなたの質問を少し誤解しました：
重みが負の場合: 木ではない可能性があります
すべての重みが負でない (>=0): 最小スパニング ツリーがありますが、ツリーではなく、同じ重みの合計を持つ別のツリーが存在する可能性があります。
すべての重みが正 (>0): ツリーです。
最小スパニング ツリー/フォレスト (MST/F) と最小スパニング グラフ (MSG) には違いがあります。
最小スパニング グラフ (MSG) : グラフ G のすべての接続されたコンポーネント内のすべてのノードを接続し、全体のコストが最小になるようにします。
負でないコストの場合、MSF は MSG に等しくなります。
たとえば、各エッジのコストが 1 の三角形として G をグラフ化します。MSG は 2 つのエッジで 3 つの頂点を接続します。これは、Kruskal、Prim、または Boruvka アルゴリズムを使用して G を計算することによって得られるのと同じ MSF です。
負のコストの場合、MSF は対応する MSG と等しくない可能性があり、さらに、MSG が常に MSF であるとは限りません。
たとえば、各エッジのコストが -1 の三角形として G をグラフ化します。MSG は、全体的なコストを削減するため、すべてのエッジを使用します。したがって、サイクルが得られます。また、定義上、ツリーまたはフォレストにはサイクルが含まれていません。正のコストを使用すると、MSG でサイクルが発生することはありません。これは、サイクルを生成するエッジを追加すると、MSG の全体的なコストが常に増加するためです。Kruskal、Prim、または Boruvka で G を計算すると、MSF が返されます。