1 有向グラフの基本概念
1.1 定義と表記
1.1.1 頂点集合と辺集合
有向グラフは、頂点集合 \(V\) と有向辺集合 \(E\) の組として与えられる。各有向辺は、ある頂点から別の頂点へ向かう“向き”を持つので、辺は始点と終点の順序対として表現できる。典型的には \[ G=(V,E),\quad E\subseteq V\times V \] の形で定義される。頂点は対象（例：タスク、状態、地点）を、辺は一方向の関係（例：依存、移動可能性、遷移）を表す。
1.1.2 隣接行列・隣接リスト
有向グラフは計算機上では主に二つの表現で扱われる。隣接行列は頂点集合の大きさを \(n\) とすると \(n\times n\) の行列で、成分は「ある頂点から別の頂点へ辺が存在するか」を記録する。疎なグラフに対しては、非ゼロ要素が少ないにもかかわらず行列全体を確保するため非効率になりやすい。
隣接リストは、各頂点ごとに“出ていく辺”の終点集合（またはリスト）を持つ方式である。辺数が頂点数に比べて少ない場合、必要な記憶量や走査の効率が良い。探索や到達計算などでの実装でしばしば用いられる。
1.2 有向辺の性質
1.2.1 ループと多重辺
ループは、頂点 \(v\) から同じ頂点 \(v\) へ向かう辺である。モデル化の目的によって、自己作用（例：状態が同じ状態に遷移し得る、タスクが自身に依存する）のような状況を表すのに利用されることがある。
多重辺は、同じ始点と終点の組に対して複数の辺が存在する場合を指す。通信路や複数の手段を同じ出発点・到着点で区別したいときに現れる。多重辺を扱うか否かは“単純性”の定義に関わるため、アルゴリズムの前提として明確にする必要がある。
1.2.2 入次数・出次数
入次数（indegree）は、ある頂点 \(v\) に向かってくる辺の本数（または重みの合計）を表す。出次数（outdegree）は、\(v\) から出ていく辺の本数（または重みの合計）である。次数情報は局所的性質を反映し、たとえば“処理待ちの量”や“分岐の数”のような直感的な意味付けが可能である。
計算機上では隣接リストからは出次数を容易に数えられることが多い。一方で入次数は、辺集合を走査し終点側で集計するなどの手順で算出できる。
1.3 有向グラフの種類
1.3.1 単純有向グラフ
単純有向グラフは、通常「ループがない」「多重辺がない」といった条件を満たす有向グラフを指すことが多い。これにより、ある頂点対の間に“辺の存在”を一度だけ記録すればよいという整理ができる。単純性は定義を簡潔にし、性質の議論でも余計な場合分けを減らせる。
ただし研究分野や応用文脈によっては、重み付きの辺を“単純性”とは別の属性として扱うこともあるため、本文脈における前提を確認することが重要である。
1.3.2 有向非巡回グラフ
有向非巡回グラフ（DAG）は、巡回（有向サイクル）を含まない有向グラフである。サイクルが存在しないことにより、依存関係や実行順序を“循環なく”整理できる状況でよく登場する。数学的には、DAGでは到達に基づく順序が矛盾なく整列でき、トポロジカルソートの適用が保証される。
DAGは計算の正当性を保つための前提条件としても用いられる。たとえば依存先が自身に戻るような定義は、DAGを破るため“循環依存”として検出対象になる。
2 到達可能性と経路
2.1 到達関係
2.1.1 到達可能性の定義
有向グラフにおける到達可能性とは、ある頂点 \(s\) から別の頂点 \(t\) へ有向辺に沿って到達できるかどうかを問う概念である。辺の向きが制約になるため、無向グラフの連結性とは異なる振る舞いを示す。
到達可能性は、経路の存在により特徴付けられる。形式的には「\(s\) から \(t\) への有向経路が存在する」ことをもって到達可能とする。これにより、ネットワークの一方向性を反映した“伝播”や“到達範囲”を記述できる。
2.1.1.1 有向経路と到達の判定
有向経路は、頂点列 \(v_0,v_1,\dots,v_k\) の列であって、各 \(i\) に対し \((v_i,v_{i+1})\in E\) が成り立つものとして定義される。開始点と終点はそれぞれ \(v_0\) と \(v_k\) である。
到達の判定は、始点から探索を行い、訪問した頂点集合の中に終点が含まれるかで行える。深さ優先探索や幅優先探索といった基本探索手法が、そのまま“到達可能集合”の計算に使える。
2.2 有向経路の性質
2.2.1 最短経路（重み付きでない場合の考え方）
重みなしの最短経路は、経路に含まれる辺の本数（あるいは段数）が最小となる経路を指す。探索の観点では、幅優先探索が自然に最短数の経路を見つける。層構造（距離 \(0,1,2,\dots\)）を順に広げることで、初めて終点に到達したとき、その段数が最小であることが保証される。
この考え方は、同じ頂点へ到達するのに“少ない手順で到達できるか”を重視する状況に適合する。たとえば最少回数の移動や最小ホップの通信路に対応する。
2.2.2 サイクル（閉路）
サイクル（閉路）は、始点と終点が同じである有向経路を含む構造として理解できる。単に同じ頂点を通るというだけでなく、辺の向きに沿って一周できることが要点である。
サイクルの有無は大きく性質を変える。たとえばDAGではサイクルが排除されるため、依存関係が循環せず、順序付けが可能になる。逆にサイクルがある場合は、実行順序や到達判定の背後に“循環”が関与し、無限繰り返しの懸念をもたらすことがある。
2.3 探索アルゴリズム
2.3.1 深さ優先探索
深さ優先探索（DFS）は、可能な限り深く辿ってから戻る方針で探索を行う。隣接リストを用いると、ある頂点から出る辺を順に辿り、未訪問の頂点があれば再帰またはスタックにより続行する。
DFSは到達可能集合の計算にも利用でき、また探索木の構造に基づいてさまざまな性質を導くことができる。具体的には訪問順や後退のタイミングが手がかりになり、サイクル検出などにも応用される。
2.3.2 幅優先探索
幅優先探索（BFS）は、始点からの距離が小さい頂点から順に訪問していく。典型的にはキューを用い、まず距離1の頂点群を処理し、その次に距離2の層へ進む。
この層型の処理は、最短経路（重みなし）の計算に直結する。さらに到達可能性の判定においても、探索が距離の増加順で進むため、到達までの段数の見積もりを自然に得られる。
3 連結性と強連結性
3.1 強連結性
3.1.1 強連結成分
強連結性は、頂点間で相互に到達できることに基づく。具体的には、頂点 \(u\) から \(v\) へ到達可能であり、同時に \(v\) から \(u\) へも到達可能であるとき、両者は強連結であるという。
強連結成分（SCC）は、強連結の関係により頂点集合を分割した塊である。強連結な頂点群の内部では行き来が可能だが、異なる成分間では片方向の到達しか起こらない構造として整理される。この分解により大規模グラフの解析が見通し良くなる。
3.1.2 強連結成分分解の意味
強連結成分分解は、グラフを互いに独立した“循環のまとまり”に置き換える操作として捉えられる。各成分を単一の頂点に縮約すると、元の複雑さが減り、上位構造としての依存関係だけが残る。
この分解は、到達可能性の解析、縮約グラフの構築、サイクルが含まれる領域の同定などに寄与する。特に、循環を含む部分と、循環がない流れの部分を区別したい場合に有効である。
3.2 弱連結性
3.2.1 辺の向きを無視した連結
弱連結性は、有向辺の向きを無視した見方で定義される。すなわち、有向グラフから向きを取り去り、得られた無向的な関係において連結であるかどうかで判断する。
この概念は、方向によって分断されるかどうかよりも、全体として“どれだけ繋がっているか”の粗い把握に向く。強連結性と比べると条件が緩いため、より大きな集合として結合されやすい。
3.3 頂点縮約と縮約グラフ
3.3.1 縮約の構成原理
縮約（contraction）は、頂点群をまとめて一つの単位に置き換える考え方である。強連結成分に関しては、同一成分内の頂点をまとめて“成分頂点”とし、元のグラフで成分 \(A\) から成分 \(B\) へ向かう辺が存在するなら、縮約後にも成分 \(A\) から \(B\) への有向辺を張る。
これにより、成分の内部で完結する循環構造は潰され、成分間の流れだけが抽出される。結果として縮約グラフは、強連結の概念を反映した階層構造を持つ。
3.3.2 縮約グラフの性質
縮約グラフは一般に、サイクルを含まない形（成分同士の“循環”が強連結性に吸収されるため）になる。つまり、縮約の後では、異なる強連結成分間の到達が循環することは起こらず、上から下へ一方向に整理される。
この性質により、縮約グラフ上での到達判定や順序付けが容易になる。たとえば成分レベルでの依存関係が明確になり、実務上も“どのまとまりがどれに影響するか”を追跡しやすくなる。
4 特別な構造と応用
4.1 トポロジカルソート
4.1.1 有向非巡回グラフとの関係
トポロジカルソートは、有向非巡回グラフの頂点を順序付けし、すべての有向辺 \((u,v)\) について \(u\) が \(v\) より前に来るようにする操作である。DAGであることが前提条件になるのは、サイクルがあると辺条件を同時に満たせないからである。
したがって、トポロジカルソートの存在はDAG性と結びつく。実装では入次数が0の頂点を繰り返し取り出す方法などがよく用いられ、順序の妥当性は辺条件が破れていないこととして確認できる。
4.1.2 値付け（順序付け）の実装上の考え方
順序付けの実装では、処理対象となる頂点集合を管理することが中心になる。入次数が0の頂点を集め、それらを出力列に追加し、取り出した頂点から出る辺によって隣接頂点の入次数を更新する。入次数が新たに0になった頂点は次の候補として追加される。
この手順により、値付け（序数の割り当て）は出力列の位置として得られる。計算量は表現方法と更新の仕方に依存するが、隣接リストを用いれば辺数の線形に近い形で処理できるのが一般的な利点である。
4.2 支配と到達の応用例
4.2.1 処理順序のモデル化
処理順序のモデル化では、タスクを頂点に、実行前提を有向辺に対応させる。たとえばあるタスク \(A\) の完了がタスク \(B\) の開始条件になるなら、辺 \(A\to B\) を置く。依存関係が循環しないなら、トポロジカルソートによって“許される実行順序”の一つを構成できる。
さらに、到達可能性を用いれば「あるタスクを先に終えたとき、どの後続タスクまで影響が及ぶか」を推定できる。これは段階的な計画やビルド手順の理解に役立つ。
4.2.2 フローの制約表現
フローの制約を有向グラフで表すと、向きは流れの方向、辺の存在は許可された移動や伝達の可能性を意味する。容量やコストなどを別属性として付与すれば、経路選択や制約充足の問題へ接続できる。
この枠組みでは、到達不可能な区間は制約によって遮断されると解釈できる。探索により“到達可能な領域”を明確化すれば、制約の影響を定性的に把握しやすくなる。
4.3 有向グラフの学術的・実務的利用
4.3.1 依存関係グラフ
依存関係グラフは、ある対象が別の対象を必要とする関係を有向辺として表す。ソフトウェアのモジュール、文章の参照、研究成果の引用など、多様な場面で“前後関係”が問題になるため、自然に適用できる。
強連結成分は、互いに参照し合って分解しにくい依存の塊を示す。縮約グラフにすることで、外部から見た依存の流れが整理され、影響範囲の分析やリファクタリングの足がかりになる。
4.3.2 状態遷移の表現
状態遷移は、システムの状態を頂点、状態から状態への変化を有向辺として表現できる。入力や条件によって遷移が選ばれる場合、辺にラベル（条件）を付与して扱うことが多い。
到達可能性は「初期状態から到達できる振る舞いの範囲」を意味し、サイクルは“状態の反復”や“安定した振る舞い”の存在に対応し得る。探索アルゴリズムによって到達可能集合を計算すれば、設計段階で想定外の挙動が含まれていないかを調べる材料になる。