3

それぞれ黒または白のエッジと整数 k を持つ接続された無向グラフがあります。正確に k 個の黒いエッジを持つスパニング ツリーが存在するかどうかを示すアルゴリズムを作成しようとしています (必ずしも実際のツリーを見つける必要はありません)。

Kruskal のアルゴリズムを使用して、スパニング ツリーの黒エッジの最小数と最大数を見つけました。k がこの範囲外の場合、k 個のエッジを持つスパニング ツリーは存在できません。

しかし、その範囲内のすべての k に対して必ずしもスパニング ツリーが存在するかどうかについて、私は頭を悩ませています。私の直感はイエスと言っており、私が試したすべての例でうまくいきましたが、それを証明する方法がわかりません.

何かアドバイス？前もって感謝します。

4

2 に答える 2

6

G_min = 黒エッジの数が最小のスパニング ツリーとします。

G_max = 黒エッジの最大数を持つスパニング ツリーとします。

k_min = G_min の黒エッジの数とする

k_max = G_max の黒エッジの数とする

証明は次のようになります。G = G_min に設定します。G_max のすべての黒いエッジに対して繰り返します。

  1) If the edge is already in G, do nothing.
  2) If the edge is not in G, add it to G and remove another edge
     from the cycle thus induced in G.  Remove one not in G_max.

ステップ 2 は、すべてのサイクルで G_max にないエッジが少なくとも 1 つあるため、常に可能です。

このアルゴリズムは、G のスパニング ツリー性を維持します。ステップごとに最大 1 つの黒エッジを追加するため、G は k_min と k_max の間のすべての k に対して k 黒エッジを持つスパニング ツリーを示します。

于 2010-12-06T07:57:33.420 に答える
1

クラスカル法は、最小のワイトスパニングツリーを検出します。したがって、Gminを検出するには、これを逆に行う必要があります。gmin =すべての黒のエッジがワイト1を与え、白がワイト0を与える場合。アルゴリズムが最初にすべての白のエッジを使用し、次に黒のエッジを使用する方法。このようにして、gminを取得します。

于 2012-05-18T07:52:09.467 に答える