概念・定理図鑑 · 基礎から応用へ

グラフの連結性:向きと到達可能性を先に決める

無向グラフの連結成分と、有向グラフの強連結・弱連結を小さな例で区別します。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 道があることを定義する
  2. 無向の連結成分を分ける
  3. 探索で一つの成分を得る
  4. 有向では相互の到達を確かめる
  5. 一時点の接続と障害耐性を分ける
  6. 孤立頂点も数える
  7. この記事をロゲイアに質問する理解を確かめる

道があることを定義する

グラフは頂点と辺で関係を表す模型です。無向グラフでは辺をどちら向きにもたどれますが、有向グラフでは矢印の向きに従います。連結性を調べる前に、どちらの模型かを決めます。物理的にケーブルがあるという情報だけでは、アプリから相手へ要求を届けられることまでは決まりません。辺を通信の許可、道路、依存などのどの関係として定義するかでも意味が変わります。ここでは経路の存在を扱い、辺の重みや遅延の最小化は別の問題としておきます。一本の経路があることと、その経路が容量や期限の要求を満たすことを同一視しません。

無向の連結成分を分ける

無向グラフで任意の二頂点の間に経路があれば、グラフは連結です。そうでなければ、互いに到達できる頂点のまとまりである連結成分へ分かれます。A―B―CとD―Eがあり、二組の間に辺がなければ、成分は{A,B,C}と{D,E}です。辺がない孤立した頂点Fを加えると、それ自身が一つの成分になります。頂点から同じ頂点へは長さ0の経路を認めるので、孤立頂点を分類から捨てません。成分を同値類として考えると、どの頂点も一つの成分に属し、二つの成分が一部だけ重ならないことを理解できます。

探索で一つの成分を得る

ある頂点からBFSまたはDFSを始め、到達した頂点を記録します。無向グラフなら、その集合が開始頂点の連結成分です。まだ訪問していない頂点を開始点として探索を繰り返すと、全成分を列挙できます。隣接リストを使い、各頂点と各辺を所定回数だけ調べる実装なら、全体の時間はO(V+E)です。一方、隣接行列で毎回すべての候補を調べるなら、同じ計算量とは限りません。表現方法と、訪問済み印を付けるタイミングを確認します。訪問済みの管理をせず同じ頂点を何度も展開すると、経路があるだけの簡単なグラフでも余計な処理が増えます。

有向では相互の到達を確かめる

A→B→Cという有向グラフでは、AからCへ到達できますがCからAへは戻れません。全頂点が一つの強連結成分になるわけではなく、この例では各頂点が別です。C→Aを加えると三頂点が相互に到達でき、一つの強連結成分になります。一方、矢印を無視して一つにつながるかを調べるのが弱連結の考え方です。最初の鎖は弱連結ですが強連結ではありません。有向グラフで一つの頂点から全頂点へ行けたという結果だけを、全組が相互に到達できる証明にしないようにします。どの向きの経路を要求するのかが結論を変えます。

一時点の接続と障害耐性を分ける

現在は経路があっても、一本の辺が消えるだけで切れるグラフがあります。そのような辺は橋と呼ばれます。A―B―Cの二辺はいずれも橋ですが、A―Cも加えた三角形では一本を失っても別経路が残ります。ただし、同じ装置を共用する複数の辺が同時に故障するなら、辺を一つずつ消す模型だけでは十分ではありません。連結である、冗長な経路がある、独立した故障領域を持つ、という三つの主張を分けます。実際の通信では経路の向き、認可、名前解決、時刻による状態変化も加わるため、図の連結性をそのままサービス稼働の保証として報告しません。

孤立頂点も数える

辺の一覧だけから頂点集合を作ると、どの辺にも現れない孤立頂点を落とす場合があります。入力で与えられた全頂点を先に登録し、辺を追加してから探索します。成分数の検算では、すべての頂点がちょうど一度分類されたことと、別成分を結ぶ辺が残っていないことを確認します。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 13

学習コースから次を選ぶ