離散数学-グラフの詳細

グラフ彩色

グラフ彩色は、隣接する頂点が同じ色にならないように、グラフGの各頂点に色を割り当てる手順です。目的は、グラフに色を付けるときに色の数を最小限に抑えることです。グラフGを着色するために必要な最小の色数は、そのグラフの彩色数と呼ばれます。グラフ彩色問題はNP完全問題です。

グラフに色を付ける方法

n個の頂点でグラフGに色を付けるために必要な手順は次のとおりです。

Step 1 −グラフの頂点をある順序で配置します。

Step 2 −最初の頂点を選択し、最初の色で色付けします。

Step 3−次の頂点を選択し、それに隣接する頂点で色付けされていない最も小さい番号の色で色付けします。隣接するすべての頂点がこの色で色付けされている場合は、それに新しい色を割り当てます。すべての頂点が色付けされるまで、この手順を繰り返します。

Example

上の図では、最初の頂点$ a $は赤で表示されています。頂点aの隣接する頂点が再び隣接しているため、頂点$ b $と頂点$ d $は、それぞれ緑と青の異なる色で色付けされます。次に、$ c $の隣接する頂点が赤に着色されていないため、頂点$ c $は赤に着色されます。したがって、グラフを3色で着色することができます。したがって、グラフの彩色数は3です。

グラフ彩色の応用

グラフ彩色のいくつかのアプリケーションは次のとおりです。

レジスタ割り当て
地図の色付け
2部グラフのチェック
モバイル無線周波数の割り当て
時間割等の作成

グラフ走査

グラフ走査は、グラフのすべての頂点を体系的な順序で訪問する問題です。グラフをトラバースするには、主に2つの方法があります。

幅優先探索
深さ優先探索

幅優先探索

幅優先探索（BFS）は、グラフ$ G $のレベル0の頂点$ X $の開始から始まります。次に、$ X $の隣にあるすべての頂点にアクセスします。訪問後、頂点を「訪問済み」としてマークし、レベル1に配置します。次に、レベル1の頂点から開始し、すべてのレベル1の頂点に同じ方法を適用します。BFSトラバーサルは、グラフのすべての頂点にアクセスすると終了します。

BFS Algorithm

概念は、隣接する頂点の他の隣接する頂点を訪問する前に、すべての隣接する頂点を訪問することです。

すべてのノードのステータスを「準備完了」として初期化します。
ソース頂点をキューに入れ、そのステータスを「待機中」に変更します。
キューが空になるまで、次の2つの手順を繰り返します-
- キューから最初の頂点を削除し、「Visited」としてマークします。
- ステータスが「準備完了」である、削除された頂点のすべてのネイバーをキューの後ろに追加します。ステータスを「待機中」としてマークします。

Problem

グラフ（ソース頂点は「a」）を取り、BFSアルゴリズムを適用してトラバーサル順序を見つけましょう。

Solution −

すべての頂点のステータスを「準備完了」に初期化します。
をキューに入れ、ステータスを「待機中」に変更します。
キューから削除し、「訪問済み」としてマークします。
追加『準備完了』状態に隣人をB、DとEキューの最後と『待機』としてそれらをマークします。
キューからbを削除し、「Visited」としてマークし、その「Ready」ネイバーcをキューの最後に配置し、cを「Waiting」としてマークします。
キューからdを削除し、「訪問済み」としてマークします。「準備完了」状態のネイバーはありません。
キューからeを削除し、「訪問済み」としてマークします。「準備完了」状態のネイバーはありません。
キューからcを削除し、「訪問済み」としてマークします。「準備完了」状態のネイバーはありません。
キューが空なので停止します。

したがって、走査順序は−です。

$ a \ rightarrow b \ rightarrow d \ rightarrow e \ rightarrow c $

トラバーサルの代替順序は次のとおりです。

$ a \ rightarrow b \ rightarrow e \ rightarrow d \ rightarrow c $

または、$ a \ rightarrow d \ rightarrow b \ rightarrow e \ rightarrow c $

または、$ a \ rightarrow e \ rightarrow b \ rightarrow d \ rightarrow c $

または、$ a \ rightarrow b \ rightarrow e \ rightarrow d \ rightarrow c $

または、$ a \ rightarrow d \ rightarrow e \ rightarrow b \ rightarrow c $

Application of BFS

最短経路を見つける
重み付けされていないグラフの最小全域木
GPSナビゲーションシステム
無向グラフでのサイクルの検出
1つの接続されたコンポーネント内のすべてのノードを検索する

Complexity Analysis

$ G（V、E）$を、頂点の数が$ | V | $で、エッジの数が$ | E | $のグラフとします。幅優先探索アルゴリズムがグラフのすべての頂点にアクセスし、すべてのエッジをチェックする場合、その時間計算量は次のようになります。

$$ O（| V | + | E |）。O（| E |）$$

$ O（1）$と$ O（| V2 |）$の間で異なる場合があります

深さ優先探索

深さ優先探索（DFS）アルゴリズムは、頂点$ v $から開始し、次に、以前に訪問したことのない隣接する頂点（たとえば、x）までトラバースし、「訪問済み」としてマークし、$ x $の隣接する頂点に進みます。など。

いずれかの頂点で、隣接するすべての頂点にアクセスした場合、これまでトラバースされたことのない隣接する頂点を持つ最初の頂点が見つかるまでバックトラックします。次に、その頂点をトラバースし、訪問したすべての頂点をトラバースして再度バックトラックする必要があるまで、隣接する頂点を続行します。このようにして、最初の頂点$ v $から到達可能なすべての頂点をトラバースします。

DFS Algorithm

概念は、他の隣接する頂点にアクセスする前に、隣接する頂点のすべての隣接する頂点にアクセスすることです。

すべてのノードのステータスを「準備完了」として初期化します
ソース頂点をスタックに配置し、そのステータスを「待機中」に変更します
スタックが空になるまで、次の2つの手順を繰り返します-
- スタックから一番上の頂点をポップし、「Visited」としてマークします
- ステータスが「準備完了」である、削除された頂点のすべての隣接ノードをスタックの一番上にプッシュします。ステータスを「待機中」としてマークします。

Problem

グラフ（ソース頂点は「a」）を取り、DFSアルゴリズムを適用してトラバーサル順序を見つけましょう。