16

無向連結グラフ G があります。少なくとも 2 つの MST がある場合に true を返すアルゴリズムを見つけたいと考えています。

正確に 2 つの MST があるかどうかを確認するにはどうすればよいですか?

4

2 に答える 2

22

Kruskal アルゴリズムを変更することで、両方のケースを効率的に検出できます。このすべてを説明する簡単な方法を誰かが考えられる場合は、お知らせください。

Kruskal は、重みが等しいエッジの順列ごとに MST を構築します。

Kruskal アルゴリズムは、これまでに構築されたフォレストのさまざまなコンポーネントを接続する次に小さいエッジを常に含めることにより、MST を構築します。このような最小エッジが選択された場合はいつでも、アルゴリズムは正しいものになります。

Kruskal はすべての MST を見つけることができます

さらに、MST は、重みが等しいエッジのすべてのセットを順序付けする特定の方法を選択してから、Kruskal アルゴリズムを実行することによって生成できます。これを確認するために、この方法では作成できない MST があったとします。次に、この MST の各エッジの重みから少量のイプシロン (等しくないエッジの重みのペア間の差よりも小さい) を減算します。この MST は一意の MST になるため、新しいエッジの重みで実行すると、Kruskal はこの MST を生成する必要があります。 . しかし、エッジを最大でイプシロンだけ調整したため、エッジが重みでソートされる場合、重み w_i を持つすべてのエッジのセット - イプシロンは、重み w_i を持つエッジのセットの直前に (何らかの順序で) 表示される必要があります (ある順序で)。 、2 つのグループの間に他のエッジはありません。しかし、これは元の変更されていないエッジの有効な可能な順序です。また、クラスカル アルゴリズムはエッジの順序のみを考慮し、特定の重みは考慮しないため、クラスカル アルゴリズムはその順序からも MST を生成したに違いありません。これは仮定と矛盾するため、クルスカル アルゴリズムはすべての MST を生成できるはずです。

コンポーネント グラフ

i >= 0 エッジ追加ステップ F(i) の後、Kruskal アルゴリズムによって構築されたフォレストを呼び出し、残りのエッジは考慮され、サイクル R(i) を作成しません。(ステップ i でエッジが追加されると、R(i-1) のコピーから始めて、追加されたばかりのエッジと同じコンポーネントのペアを結合した他のすべてのエッジを削除することにより、R(i) を形成します。アルゴリズムは実際にこれらの他のエッジを「怠惰に」削除します。このように R(i) を定義すると、アルゴリズム プロパティの証明が簡単になります。) クラスカル アルゴリズムを一連のブロックに分割します。同じ重みが追加されます。i = 0 の場合、または R(i) の最小重みエッジがステップ 1 .. i で追加されたどのエッジよりも大きい場合、 iブロック定義を呼び出します。

クラスカル アルゴリズムのブロック定義数 i >= 0 のエッジ追加ステップが実行された後、R(i) の最小エッジ (つまり、サイクルを作成しない次の最小エッジ) の重みは w であるとします。 . Kruskal アルゴリズムは、他の処理を行う前に、何らかの方法で重み w のエッジを持つすべてのツリーを結合します。これらの等しい重みのエッジに異なるエッジの順序を選択すると、生成されるツリーに影響を与える可能性がありますが、影響を与えることはできません。各ツリーの頂点のセット。これをより正確にする：

フォレスト F(i) 内の各コンポーネント (ツリー) の頂点で構成される、重み付けされていない新しいマルチグラフ (つまり、頂点の 1 つのペア間に複数のエッジを持つことができるグラフ) C(i) を定義します。C(i) の任意の頂点 v について、v に対応する F(i) のツリーを t(v) と呼びます。重み w のエッジが R(i) に存在する場合は常に、C の 2 つの頂点 u と v の間にエッジを作成します。 t(u) の頂点と t(v) の頂点の間。i ステップ後、コンポーネント グラフC(i) を呼び出します。

補題:いくつかのブロック定義番号 i に対して、C(i) が少なくとも 1 つのエッジを含む k 個のコンポーネント (つまり、単一の頂点ではないコンポーネント) を持ち、これらのコンポーネントの中に、合計で m >= 2k 個の頂点があるとします。この一連の頂点を M と呼びます。次に、等しい重みのエッジがどのように順序付けられたかに関係なく、Kruskal アルゴリズムのエッジ追加ステップを mk 回行った後、M の頂点に対応する m 個の木が k 個の木にマージされます。 1 <= j <= k ごとに、C(i) の j 番目のコンポーネントの頂点に対応するツリーの和集合と、重み w の 1 つ以上のエッジから構成される j 番目のツリー。特に、結果として得られる k 個のツリーのそれぞれの頂点のセットは、C(i) のエッジを生じさせた重み w のエッジの特定の順序付けの影響を受けません。

証拠：C(i) のすべてのエッジ (u, v) は、R(i) の重み w のエッジに対応します。これは、重みが等しいエッジの順列ですべての重み w のエッジの中で最初に現れる可能性があるため、次の式によって次に選択できます。クラスカルアルゴリズム。これを追加すると、F(i) の 2 つのツリーが F(i+1) の 1 つに結合され、R(i+1) から 1 つまたは複数のエッジが破棄されます。コンポーネント グラフへの影響は、C(i) の u と v を C(i+1) の単一の頂点 x にマージし、C(i+1) の u と v の間の他のすべての平行エッジを削除し、変更することです。 C(i) の 3 番目の頂点 y と u または v の間のすべてのエッジを、C(i+1) の y と新しい頂点 x の間のエッジにします。C(i) の 1 つのコンポーネントのエッジが次に Kruskal によって選択された場合、他のコンポーネントのエッジは影響を受けないため、異なるコンポーネントのエッジが順列でどのようにインターリーブされるかは影響しません。したがって、1 つのコンポーネントのすべてのエッジが最初に表示され、次に別のコンポーネントのすべてのエッジが表示され、k 番目のコンポーネントまで同様に表示されると想定できます。最初のコンポーネントに s 個の頂点があるとします。Kruskal アルゴリズムによって追加された各エッジは、コンポーネントを切断することなく、このコンポーネントの頂点の数を 1 減らします。C(i+j) のコンポーネントにエッジが存在することは、F(i+j) の 2 つの異なるツリーを接続する R(i+j) に重み w のエッジが存在することを示しているため、Kruskal アルゴリズムは続行されます。 C(i+s-1) で単一の頂点になるまで、このコンポーネントを縮小するエッジを選択します。各ステップでどのエッジが選択されるかに関係なく、F(i+s-1) の対応するツリーの頂点は、F(i) の s ツリーのすべての頂点の和集合で構成されます。これは、残りのコンポーネントに対して繰り返すことができます。

MST のカウント

定理: MST の数は、各ブロック定義 i のマルチグラフ C(i) 内のスパニング フォレストの数の積です。

証拠：補題で確立されているように、C(i) のエッジの順列で Kruskal を実行することによって生成できるすべてのフォレストは、F(i+mk) の結果として得られる各ツリー コンポーネントの頂点のセットに関して同一です。C(i) の s-頂点コンポーネントの各スパニング ツリーは、F(i) の s ツリーの対応するセットを含む個別の基になる MST を生成するために、Kruskal アルゴリズムによって選択できる s-1 エッジの個別のセットを表します。 . スパニング フォレストは、コンポーネントごとに 1 つのスパニング ツリーの組み合わせであるため、スパニング フォレストの数は、含まれる各ツリーのスパニング ツリーの数の積になります。C(i) q(i) でスパニング フォレストの数を呼び出します。後続の Kruskal ブロッ​​クのエッジ追加ステップでは、各コンポーネントのエッジ構造は考慮されず、各コンポーネントの頂点のみが考慮されるため、

imslavko によって与えられたKirchhoff の定理に基づくものなど、グラフの全域木の数を計算するためのやや複雑なアルゴリズムがあります。それがマルチグラフで機能するかどうかはわかりません。しかし、いずれにせよ、特定のケース 1、2、および 2 以上のみに関心があるため、近道をすることができます。

  • グラフが正確に 1 つの MST を持っているか、1 を超えているかだけを検出したい場合、整数の積が 1 になる唯一の方法は、すべての因子が 1 に等しい場合であるという事実を使用できます。 C(i) に複数のスパニング ツリーがある場合は、すぐに停止して "複数" と報告します。これが発生せずに終了した場合は、「1」と報告してください。

  • グラフに正確に 2 つの MST があるかどうかを検出したい場合、整数の積が 2 に等しくなるためには、因子の 1 つだけが 2 に等しく、残りはすべて 1 でなければならないという事実を使用できます。 multigraph が正確に 2 つのスパニング ツリーを持つようにするには、フォレストと、それらの間に既にエッジがある 2 つの頂点間にちょうど 1 つの追加の (平行な) エッジで構成されている必要があります。(k >= 3 の k サイクルを含むマルチグラフには、k 個のエッジのいずれか 1 つを削除することによって形成される、少なくとも k 個のスパニング ツリーが必要です。)

アルゴリズムの概要

通常どおり Kruskal を実行しますが、新しいブロックが開始されるたびに (以前に追加されたエッジよりも重みが大きいエッジが追加されることで示されます)、エッジを追加する前に、次の手順を実行します。

  1. 隣接リスト表現を使用して、空のマルチグラフ C を作成します。
  2. この重みを持つ残りのすべてのエッジを順方向にスキャンし、各エッジ (u, v) について (c(u), c(v)) を C に追加します。ここで、c(v) は和集合によって見つかった v の代表ノードです。 /find 接続を確認するために使用されている構造。
  3. フラグの配列を使用して、どの頂点が既にアクセスされたかを記録して、このマルチグラフの各コンポーネントを介して DFS を実行します。この DFS の目的は、サイクルと並列エッジをチェックすることです。
    • 長さが 3 以上のサイクルがある場合、コンポーネントには少なくとも 3 つのスパニング ツリーがあり、アルゴリズムはこの時点で終了できることを意味します。
    • 多重度が 3 以上の平行なエッジが現れた場合、アルゴリズムは同様にすぐに終了する可能性があります。
    • 2 つの頂点間にダブルエッジが見られるたびに、グローバル カウンターをインクリメントします。このカウンターが 1 を超えた場合、少なくとも 2*2 = 4 つの MST が存在するため、アルゴリズムは再びすぐに終了します。Kruskal アルゴリズムの最後に到達し、カウンターが 1 の場合、正確に 2 つの MST が存在します。それ以外の場合は 0 でなければなりません。この場合、正確に 1 つの MST が存在します。

これらの追加操作はすべて、エッジのバラバラなブロックで線形時間を要するため、基礎となるクラスカル アルゴリズムの時間の複雑さが O(E log V) を超えて増加することはありません。

于 2012-12-08T15:57:08.107 に答える
2

異なるスパニング ツリーの数を決定するアルゴリズムを知っています。このアルゴリズムはキルヒホッフの定理を使用しています。最小ツリーの数に関する問題を解決したことを覚えていますが、記憶が正しければ指数関数的でした。主なアイデアは、ツリーと包含-除外メソッドで使用されるエッジのビット マスクをテストすることでした。

ちなみに、すべての辺の重みが異なる場合、MST は 1 つしかありません。それが役に立てば幸い。

于 2012-12-08T01:48:21.137 に答える