0

連結グラフGが与えられた場合、グラフをGaとGbに分割します。GaとGbの最小スパニングツリー（それぞれXaとXbと呼ばれる）を見つけた場合、最小の重み付きエッジでXaをXbに接続しても、スパニングツリーが形成されますか？そのスパニングツリーは最小スパニングツリーですか？

これが私のこれまでの論理です。XaをXbに接続すると、ほぼ定義上、少なくともスパニングツリーが形成されると思います。（カウンターサンプルがある場合は便利ですが）ただし、グラフの構造によっては、XaまたはXbからエッジを削除できる場合があるため、常に最小スパニングツリーが形成されるとは限りません。次に、それらを接続するエッジを追加しますが、それでもツリーがあります。これは、同じ重みの複数のエッジが異なる頂点でXaとXbを接続する状況の場合です。

私の論理は今のところ正しいですか？

4

2 に答える 2

1

正しいのは、XaとXbを接続するだけでは、常に最小スパニングツリーが得られるとは限らないということです。ただし、XaとXbを接続するエッジの重みが同じである必要はありません。次の例を参照してください。

次のグラフGがあると仮定します。

A-B-C-D 
| | | | 
E-F-G-H

エッジ（B、C）のコストは1で、（F、G）のコストは2で、他のすべてのエッジのコストは10です。

次に、それをGaとGbに分割します。

A-B   C-D 
| |   | | 
E-F   G-H

最小全域木XaおよびXbは次のとおりです。

A-B   C-D 
|       | 
E-F   G-H

ここでそれらを可能な限り最小限のエッジで接続すると、コスト61のスパニングツリーが得られます。

A-B-C-D 
|     | 
E-F G-H

しかし、それは最小限のスパニングツリーではありません。最小スパニングツリー（コスト53）は次のようになります

A-B-C-D 
|       
E-F-G-H
于 2012-04-01T22:34:28.480 に答える
0

完全ではありません。解決策を想定し、反例をリバースエンジニアリングする必要があります。たとえば、グラフGの場合、最小全域木はXであると仮定します。

  • Xを1回だけカットするようにグラフを分割した場合、最小の重み付きエッジは必然的に削除されたエッジになるため、反例を作成することはできません。
  • ただし、パーティションがツリーを2箇所で切断する場合は、反例があります。1つのエッジを追加するだけでよいと主張しますが、構築によって最適なツリーを2つの場所でカットするため、最適なツリーを再構築するために2つのエッジを追加する必要があります（また、1つのエッジに無関係なエッジがありますパーティション）。（これの非常に明確な例については、stecklの回答を参照してください。）

あなたの最初の主張（「XaをXbに接続すると、ほぼ定義上、少なくともスパニングツリーが形成されると思います。」）は正しいです。ツリーに関するいくつかの事実を使用してそれを証明できます。NノードとN-1エッジを持つ完全接続グラフはツリーであり、ツリーはNノードとN-1エッジを持つ完全接続グラフです（サイクルは形成できません）。または、 http：//en.wikipedia.org/wiki/Tree_ （graph_theory）#Definitionsから同等の条件を使用できます

于 2012-04-01T22:32:47.620 に答える