私は、黒または白の各辺と整数kを持つ無向グラフを接続しています。 私は、正確にk個の黒い辺を持つスパニングツリーが存在するかどうかを示すアルゴリズムを記述しようとしています（必ずしも実際のツリーを見つける必要はありません）。正確にk個の色付きエッジを持つスパニングツリー
私はスパルスツリーの黒いエッジの最小数と最大数を見つけるためにKruskalのアルゴリズムを使用しました。 kがこの範囲外の場合、k個のエッジを持つスパニングツリーは存在しません。
しかし、私は、その範囲内のすべてのkに対して必ずスパニングツリーが存在するかどうかを心配しています。私の直感はそう言います、私が試したすべての事例でうまくいっていますが、それを証明する方法を理解することはできません。
アドバイスはありますか？前もって感謝します。
G_min =スパニングツリーで、黒いエッジの最小数を＃とします。
G_max =黒いエッジの最大数を持つスパニングツリーとします。
はG_min
における黒エッジのk_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ステップにつき最大1つの黒いエッジを追加するので、Gはk_minとk_maxの間のすべてのkについてk個の黒いエッジを有するスパニングツリーを示す。
G_maxには少なくとも1つのエッジがありますが、新しいグラフはツリーではありません。 （サイクルを持つことも、切断することもできます）。 –
@Saeed：ステップ2は唯一のサイクルからエッジを削除するため、サイクルを持つことはできません。ツリーの適切な辺数を持つため（アルゴリズムは常に別の辺を追加してアルゴリズムを置き換えます）、サイクルを持たないため、切断できません。 –
Kruskal'sはあなたに最低限のスパニングツリーを見つけます.Gminを見つけるために、逆にこれを行う必要があります。 gmin = caseすべての黒いエッジがワイト1を与え、白がワイト0を与えます。アルゴリズムは最初にすべての白いエッジと黒のエッジを使います。この方法で我々はgminを得るでしょう。
Kruskalアルゴリズムで黒いエッジの最小数と最大数をどのように見つけるか？ –
申し訳ありませんが、私はノードが黒または白であると思います、あなたは端を言っています。 –