最小スパニングツリー：カットプロパティ
1. 概要
このチュートリアルでは、最小全域木のカットプロパティについて説明します。
さらに、カットのいくつかの例を示し、最小スパニングツリーでのカットプロパティの正確さについても説明します。
2. カットの定義
グラフ理論では、カットは、グラフを2つの互いに素なサブセットに分割するパーティションとして定義できます。
正式にカットを定義しましょう。 連結グラフのカットは、頂点セットを2つの互いに素なサブセットに分割します。
グラフ理論では、この説明中に発生するカットに関連するいくつかの用語があります。カットセット、カット頂点、およびカットエッジです。先に進む前に、ここでこれらの定義について説明します。
連結グラフのカットのカットセットは、一方の端点がに、もう一方の端点がにあるエッジのセットとして定義できます。 たとえば、
連結グラフが存在する場合、頂点は切断点であり、から削除するとそのグラフが切断されます。
エッジは、グラフを切断する場合、接続されたグラフのカットエッジです。
3. 例
このセクションで、
まず、連結グラフを見てみましょう。
ここでは、どことを取りました。 次に、カットを定義しましょう：
したがって、ここでは、カットによってグラフが切断され、2つのコンポーネントとに分割されます。
次に、切断点について説明します。 定義によれば、切断点を削除するとグラフが切断されます。 グラフを観察すると、との2つのカット頂点があることがわかります。これを確認しましょう。 まず、頂点を次の場所から削除します。
頂点を削除するとグラフが切断され、2つのグラフに分割されることがわかります。 したがって、それがの切断点であることを確認しました。 次に、頂点を次の場所から削除しましょう。
繰り返しますが、から削除すると、グラフが切断され、2つのグラフが作成されます。 したがって、はの切断点でもあります。
カットエッジについて話しましょう。 定義によれば、カットエッジを削除すると、グラフが切断され、2つ以上のサブグラフが作成されます。 では、エッジ がカットエッジであることが簡単にわかります。から削除すると、グラフが2つのサブグラフに分割されます。
次はカットセットです。 カットのカットセットは、2つの端点が2つのグラフにあるエッジのセットとして定義されます。 ここで、のカットのカットセットはになります。 の一方のエンドポイントがに属し、もう一方のエンドポイントがにあることがわかります。
4. カットのバリエーション
カットには、最大カットと最小カットの2つの一般的なバリエーションがあります。このセクションでは、これら2つのバリエーションについて例を挙げて説明します。
最小カットと最大カットの両方が、重み付き連結グラフに存在します。 最小カットは、削除するとグラフが切断されるエッジの重みの最小合計です。 同様に、最大カットは、グラフを削除するとグラフが切断されるエッジの重みの最大合計です。
最大カットと最小カットを見つけましょう：
ここでは、接続された重み付きグラフを使用しています。 また、グラフに4つのカットを定義しました。
したがって、定義に従って、各カットのエッジの重みを合計します。 から始めましょう。 の重みの合計でのエッジの合計重み。 このように、との重みはになります。
したがって、最小カットはで、重みは6 であり、
5. 最小スパニングツリーのカットプロパティ
5.1. 声明
これで、カットによってグラフの頂点セットが2つ以上のセットに分割されることがわかりました。 カットセットには、一方の端点が1つのグラフにあり、もう一方の端点が別のグラフにあるエッジのセットが含まれています。 最小スパニングツリー（MST）を構築する場合、元のグラフは重み付けされた連結グラフである必要があります。 MSTのすべてのエッジコストが異なると仮定しましょう。
カットプロパティによると、カットセット内の他のすべてのエッジの中でエッジの重みまたはコストが最小のエッジがカットセット内にある場合、そのエッジは最小全域木に含まれる必要があります。
5.2. 例
ここでは、加重連結グラフを使用しています。
この例では、カットによってグラフが2つのサブグラフ（緑の頂点）と（ピンクの頂点）に分割されています。 のカットセットはです。 ここで、カットプロパティに従って、カットセットからの最小加重エッジがの最小スパニングツリーに存在する必要があります。 ここで、カットセットからの最小加重エッジはです。
次に、の最小全域木を構築し、エッジが存在するかどうかを確認します。
これは、の最小全域木の1つであり、ご覧のとおり、ここにエッジがあります。 したがって、カットプロパティはグラフに対して正常に機能すると言えます。
他のグラフはどうですか？ カットプロパティは他のすべての最小全域木にも当てはまりますか？次のセクションで調べてみましょう。
5.3. カットプロパティの証明
ここで、cutプロパティがすべての最小スパニングツリーで機能すると結論付けるために、このセクションで正式な証明を提示します。
グラフから最小全域木を構築すると仮定しましょう。 また、頂点セットを2つのセットとに分割するカットを定義しました。 さらに、2つのセットを結合するエッジが存在し、重みが最小であると仮定します。
ここで、エッジがMSTの一部ではないと仮定してこの証明を開始します。 MST。 に含めると、サイクルが作成されます。 ただし、MSTの定義によれば、サイクルをMSTの一部にすることはできません。
ここで、MSTを分析する場合、にエッジが必要です。これに1つのエンドポイントがあり、別のエンドポイントがにある以外の名前を付けましょう。 ここで、最初は、とを結合するすべてのエッジの中で最小の重みを持つと仮定しました。 これは、エッジがよりも重い必要があることを意味します。
したがって、スパニングツリーはありますが、最小スパニングツリーはありません。エッジを含めてMSTを構築すると、MSTの総重みは前の重みよりも小さくなります。 また、両方を含めることはできません。これにより、サイクルが作成されます。 したがって、MSTの一部ではない最初の仮定は間違っているはずです。
したがって、カットセットの最小重み付きエッジは、そのグラフの最小スパニングツリーの一部である必要があると結論付けることができます。
例を使って証明を単純化してみましょう。
接続された加重グラフを使用しています。 次に、カットを定義しましょう：
カットはグラフを2つのサブグラフとに分割しました。 これで、接続する2つのエッジがあり、その中に最小の重み付きエッジがあります。 まず、エッジを含めずに最小全域木を構築します。
ここでの最小全域木の総重量はです。 以前、カットセットの最小加重エッジを定義しました。 これは、エッジの重みがエッジよりも大きくなければならないことを意味します。 このような場合、現在構築されているスパニングツリーはMSTではありません。これは、現在のスパニングツリーよりも重みを小さくできるスパニングツリーを構築できるためです。
ご覧のとおり、スパニングツリーにエッジを含めると、スパニングツリーの総重みは、エッジを含めて構築したときの重みよりも大きくなります。 したがって、エッジ、を含めると、最小スパニングツリーにはなりません。
したがって、接続された重み付きグラフに対応する最小全域木には、カットセットの最小重み付きエッジが含まれている必要があることを証明しました。
5.4. 応用
PrimのアルゴリズムやKruskalのアルゴリズムなどの最短経路アルゴリズムは、cutプロパティを使用して最小スパニングツリーを構築します。
6. 結論
このチュートリアルでは、最小全域木でのカットプロパティについて説明しました。
カットプロパティの正しさを提示し、カットプロパティがすべての最小全域木に有効であることを示しました。
