グラフが二部グラフかどうかのチェック方法
二部グラフとは何か、BFS二色塗りを使用して二部性をチェックする方法を学びます。奇数サイクルとの関連、マッチング問題、実用的な応用を理解します。
Graph Properties
詳細な説明
二部グラフ
グラフが二部グラフであるとは、頂点を2つの互いに素な集合UとVに分割でき、すべての辺がUの頂点とVの頂点を接続する場合です。同値的に、グラフが二部グラフであるのは奇数長のサイクルを含まない場合に限ります。
二色塗りアルゴリズム
二部性のチェックは、グラフが2色で塗れるかのチェックと等価です：
- 任意のノードからBFS/DFSを開始し、REDに色を塗る
- すべての隣接ノードをBLUEに色を塗る
- それらの未着色の隣接ノードをREDに色を塗る
- 現在のノードと同じ色の隣接ノードが見つかったら二部グラフではない
- 未訪問の各成分について繰り返す
時間計算量
O(V + E) — すべてのノードと辺を1回ずつ訪問するため。
応用
- マッチング問題 — 仕事と労働者、学生と学校の割り当て
- スケジューリング — 2グループ（時間枠とイベント）の互換性辺
- コンフリクト検出 — 二部グラフでなければ避けられない競合がある
ユースケース
仕事割り当て問題は労働者とタスクを二部グラフとしてモデル化し、最適マッチングを発見します。ネットワークフロー問題は二部マッチングに分解されることが多いです。画像セグメンテーションアルゴリズムはピクセルグラフの二部性をチェックします。試験スケジューリングは時間枠の競合を検出するために二部チェックを使用します。