Discrete-mathematics-more-on-graphs
離散数学-グラフの詳細
グラフの色付け
グラフの色付けは、隣接する頂点が同じ色にならないように、グラフGの各頂点に色を割り当てる手順です。 目的は、グラフの色付け中に色の数を最小限にすることです。 グラフGの色付けに必要な最小の色数は、そのグラフの色数と呼ばれます。 グラフの色付けの問題は、NP完全問題です。
グラフを着色する方法
n個の頂点を持つグラフGを着色するために必要な手順は次のとおりです-
- ステップ1 *-グラフの頂点を何らかの順序で配置します。
- ステップ2 *-最初の頂点を選択し、最初の色で色付けします。
- ステップ3 *-次の頂点を選択し、隣接する頂点で色付けされていない最も小さい番号の色で色付けします。 隣接するすべての頂点がこの色で色付けされている場合、新しい色を割り当てます。 すべての頂点が色付けされるまで、この手順を繰り返します。
例
上の図では、最初の頂点$ a $は赤で色付けされています。 頂点aの隣接する頂点が再び隣接するため、頂点$ b $と頂点$ d $はそれぞれ異なる色、緑、青で色付けされます。 次に、$ c $の隣接する頂点が赤に着色されないため、頂点$ c $は赤に着色されます。 したがって、グラフを3色で着色できます。 したがって、グラフの色数は3です。
グラフ彩色の応用
グラフの色付けのいくつかのアプリケーションが含まれます-
- https://en.wikipedia.org/wiki/Register_allocation [割り当ての登録]
- 地図の色付け
- 二部グラフのチェック
- https://www.zib.de/groetschel/teaching/SS2012/GraphCol%20and%20FrequAssignment.pdf [モバイル無線周波数の割り当て]
- タイムテーブルの作成など
グラフトラバーサル
グラフトラバーサルは、ある系統的な順序でグラフのすべての頂点を訪れる問題です。 グラフをトラバースするには、主に2つの方法があります。
- 幅優先検索
- 深さ優先検索
幅優先検索
幅優先検索（BFS）は、グラフ$ G $の開始レベル0頂点$ X $から始まります。 次に、$ X $の近傍であるすべての頂点を訪問します。 訪問後、頂点を「訪問済み」としてマークし、レベル1に配置します。 次に、レベル1の頂点から開始し、すべてのレベル1の頂点などに同じメソッドを適用します。 グラフのすべての頂点が訪問されると、BFS走査は終了します。
- BFSアルゴリズム*
概念は、すべての近隣頂点を訪問してから、近隣頂点の他の近隣頂点を訪問することです。
- すべてのノードのステータスを「準備完了」として初期化します。
- ソース頂点をキューに入れ、ステータスを「待機中」に変更します。
- キューが空になるまで、次の2つの手順を繰り返します-
- キューから最初の頂点を削除し、「Visited」としてマークします。
- ステータスが「準備完了」である削除された頂点のすべてのネイバーをキューの後ろに追加します。 ステータスを「待機中」としてマークします。
問題
グラフ（ソース頂点は「a」）を取得し、BFSアルゴリズムを適用して走査順序を見つけましょう。
ソリューション-
- すべての頂点のステータスを「準備完了」に初期化します。
- _a_をキューに入れて、ステータスを「待機中」に変更します。
- キューから_a_を削除し、「訪問済み」としてマークします。
- 「準備完了」状態の_a_のネイバー_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 $
- BFSの適用*
- 最短経路を見つける
- 重み付けされていないグラフの最小スパニングツリー
- GPSナビゲーションシステム
- 無向グラフでのサイクルの検出
- 1つの接続されたコンポーネント内のすべてのノードを見つける
複雑さの分析
$ G（V、E）$を$ | V | $個の頂点と$ | E | $個のエッジを持つグラフとします。 幅優先探索アルゴリズムがグラフ内のすべての頂点を訪れ、すべてのエッジをチェックする場合、その時間の複雑さは次のようになります-
O（| V | + | E |）。 O（| E |）
$ O（1）$と$ O（| V2 |）$の間で異なる場合があります
深さ優先検索
深さ優先探索（DFS）アルゴリズムは頂点$ v $から始まり、それまでに訪れたことのない隣接する頂点（xなど）に移動し、「訪問済み」としてマークし、$ x $の隣接する頂点で続行します。など。
いずれかの頂点で、すべての隣接する頂点にアクセスした場合、それは、以前に横断されていない隣接する頂点を持つ最初の頂点が見つかるまでバックトラックします。 次に、その頂点をトラバースし、訪問したすべての頂点をトラバースし、再びバックトラックする必要があるまで、隣接する頂点で続行します。 このようにして、初期頂点$ v $から到達可能なすべての頂点をトラバースします。
- DFSアルゴリズム*
概念は、他の隣接頂点を訪問する前に、隣接頂点のすべての隣接頂点を訪問することです。
- すべてのノードのステータスを「準備完了」として初期化する
- ソース頂点をスタックに配置し、そのステータスを「待機中」に変更します
- スタックが空になるまで、次の2つの手順を繰り返します-
- スタックから頂点をポップし、「Visited」としてマークします
- ステータスが「準備完了」である削除された頂点のすべての隣接ノードをスタックの一番上にプッシュします。 ステータスを「待機中」としてマークします。
問題
グラフ（ソースの頂点は「a」）を取得し、DFSアルゴリズムを適用して走査順序を見つけましょう。
溶液
- すべての頂点のステータスを「準備完了」に初期化します。
- スタックで_a_をプッシュし、ステータスを「待機中」に変更します。
- _a_をポップし、「訪問済み」としてマークします。
- a_の「準備完了」状態の隣人_e、d、および_b_をスタックの一番上にプッシュし、「待機中」としてマークします。
- スタックから_b_をポップし、「Visited」としてマークし、その「Ready」ネイバー_c_をスタックにプッシュします。
- スタックから_c_をポップし、「訪問済み」としてマークします。 「準備完了」の隣人はいません。
- スタックから_d_をポップし、「訪問済み」としてマークします。 「準備完了」の隣人はいません。
- スタックから_e_をポップし、「Visited」としてマークします。 「準備完了」の隣人はいません。
- スタックは空です。 やめて
したがって、走査順序は-
$ a \ rightarrow b \ rightarrow c \ rightarrow d \ rightarrow e $
トラバースの代替順序は次のとおりです-
$ a \ rightarrow e \ rightarrow b \ rightarrow c \ rightarrow d $
または、$ a \ rightarrow b \ rightarrow e \ rightarrow c \ rightarrow d $
または、$ a \ rightarrow d \ rightarrow e \ rightarrow b \ rightarrow c $
または、$ a \ rightarrow d \ rightarrow c \ rightarrow e \ rightarrow b $
または、$ a \ rightarrow d \ rightarrow c \ rightarrow b \ rightarrow e $
複雑さの分析
$ G（V、E）$を$ | V | $個の頂点と$ | E | $個のエッジを持つグラフとします。 DFSアルゴリズムがグラフ内のすべての頂点を訪問し、すべてのエッジをチェックする場合、時間の複雑さは-
\ circleddash（| V | + | E |）
アプリケーション
- グラフでのサイクルの検出
- トポロジカルソートを見つけるには
- グラフが二部かどうかをテストするには
- 接続されたコンポーネントの検索
- グラフの橋を見つける
- グラフで双連結性を見つける
- ナイトのツアーの問題を解決する
- たった1つのソリューションでパズルを解く
