グラフが2部グラフであるかどうかを確認する方法は？
1. 概要
グラフ理論では、2部グラフは2つの頂点セットで構成される特殊な種類のグラフです。 このチュートリアルでは、一般的な定義について説明します。 また、特定のグラフが2部グラフであるかどうかを判断するためのアルゴリズムも示します。
2. 2部グラフの定義
グラフを考えてみましょう。 次の場合、グラフは2部グラフになります。
さらに単純化してみましょう。 グラフでは、2つの分割された頂点セットとがあります。 エッジがあるとします。 2部グラフの定義によれば、エッジはセットから1つの頂点に接続し、セットから別の頂点に接続する必要があります。
3. 例
2部グラフの例を見てみましょう。
ここでは、ランダムグラフを取りました。 ここで、2部グラフの定義を満たすには、各エッジが2つの頂点セットを結合するように頂点セットを2つのセットに分割する必要があります。
2部グラフの定義を満たすようにの頂点セットを分割することは可能ですか？ 確認してみましょう：
これは同じグラフですが、表現が異なります。 ここでは、頂点セットを2つの互いに素な頂点セットとに分割します。
また、エッジセットのエッジが2部グラフの定義に従っていることがわかります。 各エッジには、に1つのエンドポイントがあり、に別のエンドポイントがあります。 両方の端点がまたはに属するエッジはありません。
したがって、グラフは2部グラフであると結論付けることができます。
4. プロパティ
2部グラフには、いくつかの非常に興味深い特性があります。 このセクションでは、2部グラフのいくつかの重要なプロパティについて説明します。
グラフが2部グラフの場合、奇数サイクルが含まれることはありません。
グラフでは、ランダムサイクルはになります。 もう1つはです。
サイクルの長さは、それに含まれる個別の頂点の数として定義されます。 上記の両方のサイクルで、頂点の数はです。 したがって、これらは偶数サイクルです。
2部グラフのサブグラフも2部グラフです。
グラフで、ランダムな部分グラフを選択しましょう。 ここと。 このサブグラフも2部グラフです。
2部グラフは常に2色であり、その逆も同様です。
グラフ彩色の問題では、2色可能とは、隣接する2つの頂点が同じ色にならないように、異なる色を使用してグラフのすべての頂点に色を付けることができることを意味します。
2部グラフの場合、2つの頂点セットがあり、各エッジには各頂点セットに1つの端点があります。 したがって、すべての頂点に異なる色を使用して色を付けることができ、隣接する2つのノードが同じ色になることはありません。
無向2部グラフでは、各頂点分割セットの次数は常に等しくなります。
グラフの例では、パーティションは次のとおりです。および。 これで、頂点の次数の合計とがセットの次数になります。 どちらも程度です。 したがって、の次数はです。
の次数は、頂点、、、およびの次数の合計です。 頂点、、、およびはそれぞれ次数です。 したがって、集合の次数はです。 2部グラフと同様に、2つの頂点分割セットの次数は同じ次数です。
5. アルゴリズム
このセクションでは、特定のグラフが2部グラフであるかどうかを判断するアルゴリズムを紹介します。
このアルゴリズムは、グラフ彩色と BFS の概念を使用して、特定のグラフが2部グラフであるかどうかを判断します。
このアルゴリズムは、グラフと開始頂点を入力として受け取ります。 アルゴリズムは、入力グラフが2部グラフであるか、グラフが2部グラフではないかのいずれかを返します。
このアルゴリズムの手順は次のとおりです。
- 開始頂点に赤い色を割り当てます
- 開始頂点の近傍を見つけて、青色を割り当てます
- 隣人の隣人を見つけて、赤い色を割り当てます
- グラフ内のすべての頂点に色が割り当てられるまで、このプロセスを続けます
- このプロセス中に、隣接する頂点と現在の頂点の色が同じである場合、アルゴリズムは終了します。 アルゴリズムは、グラフが2部グラフではないことを返します
キューデータ構造を使用して、すべての隣接する頂点を格納および管理しました。
6. グラフでのアルゴリズムの実行
このセクションでは、サンプルグラフでアルゴリズムを実行して、アルゴリズムが正しい出力を提供することを確認します。
サンプルグラフを取得しました。頂点セットには頂点があります。 ここでは、開始頂点として頂点を選択しています。 それでは、最初のステップを始めましょう。
したがって、アルゴリズムの最初のステップは、開始頂点を赤い色で塗りつぶすことです。 次のステップは、頂点の隣接する頂点を見つけて、それらを青色で塗りつぶすことです。
頂点には2つの隣接する頂点があります：と。 アルゴリズムは最初に、隣接する頂点がすでに色で塗りつぶされているかどうかをチェックします。 私たちの場合、それらは埋められていません。 アルゴリズムは頂点を青色で塗りつぶします。
次に、新しく塗りつぶされた頂点のいずれかを選択し、隣接する頂点を見つけます。 頂点を選択しましょう：
グラフでは、頂点は頂点とに隣接しています。 ここで、アルゴリズムは最初に頂点がすでに何らかの色で塗りつぶされているかどうかをチェックします。 私たちの場合、頂点は色で塗りつぶされていません。
次に、アルゴリズムは頂点の色をチェックします。 の色は青なので、アルゴリズムは赤で塗りつぶされます。
ここで、アルゴリズムは隣接する頂点のをチェックします。 頂点には2つの隣接する頂点があります：と。 この場合も、アルゴリズムは頂点がすでに色で塗りつぶされているかどうかをチェックします。 この場合、頂点はすでに色で塗りつぶされています。 しかし、頂点はまだ埋められていません。
アルゴリズムは頂点の色をチェックします。 頂点が青色で塗りつぶされると、アルゴリズムは頂点を赤色で塗りつぶします。 アルゴリズムは、すべての頂点とその隣接頂点を1回チェックするまで、このプロセスを続行します。
これで、グラフで、隣接する頂点に同じ色がないことがわかります。 また、頂点セットの2つの明確なパーティションを見ることができます：と。
したがって、アルゴリズムはグラフが2部グラフであることを返します。
7. 時間計算量分析
アルゴリズムでは、最初に、各頂点を1回トラバースします。 次に、頂点ごとに、頂点の各隣接頂点に1回アクセスします。 アルゴリズムはトラバースにBFSを使用します。 BFSには時間がかかります。
頂点を格納するために、隣接行列または隣接リストのいずれかを使用できます。
ここで、隣接行列を使用する場合、グラフの頂点をトラバースする必要があります。 したがって、隣接行列を使用する場合、アルゴリズムの全体的な時間計算量はになります。
一方、隣接リストは、グラフ内のすべての頂点とその隣接頂点をトラバースするのに時間がかかります。 したがって、アルゴリズムで隣接リストを使用すると、全体的な時間計算量はになります。
8. 結論
このチュートリアルでは、2部グラフについて詳しく説明しました。
グラフが2部グラフであるかどうかを判断するために、グラフ彩色ベースのBFSアルゴリズムを紹介しました。
最後に、与えられたアルゴリズムの時間計算量を分析しました。
