1 グラフ到達の基本概念
グラフ到達は、グラフのある頂点から出発して、辺に沿って頂点をたどることで別の頂点に至れるかどうかを扱う考え方である。判定対象は「到達できるか」という可否に加え、どの頂点が到達可能かという集合としても整理される。
到達の議論は、数学的な定義の明確化と、計算機上での判定手続きの設計の両面を持つ。経路の存在に着目し、形式的な条件に基づいて到達可能性を評価する点が基本となる。
1.1 到達可能性（リーチャビリティ）の定義
有向グラフまたは無向グラフにおいて、頂点 \(u\) から頂点 \(v\) へ「到達可能」であるとは、\(u\) から出発して、辺を順にたどって \(v\) に到達できることである。到達可能性は、しばしば \(u\) から \(v\) への到達関係として表現される。
定義の厳密化では、「たどる」の対象が辺のみであり、頂点の重複を許してよいか、また経路の長さをどう扱うかが整理される。通常は「辺を連続的にたどる」ことにより、有限長の経路が存在するかどうかで到達可能性を定める。
1.2 経路と隣接関係
経路は、頂点の列 \((v_0, v_1, \dots, v_k)\) と、その連続する頂点対 \((v_i, v_{i+1})\) を結ぶ辺が存在することによって表される。したがって経路の存在は、「連続する各ステップで辺がある」という局所条件の連鎖として捉えられる。
隣接関係は、ある頂点から直接たどれる頂点の集合を与える概念である。到達可能性はこの隣接関係を繰り返し適用した結果として理解でき、最初の一手（隣接）から出発して、次の一手、さらにその次へと拡張することで到達集合が形成される。
1.3 無向グラフと有向グラフでの違い
無向グラフでは、辺は両方向に移動可能とみなされるため、経路は反対向きにたどることも可能である。その結果、到達関係の見え方は対称的になりやすい。
有向グラフでは、辺が向きを持つため、同じ頂点対でも片方向にしか移動できない場合がある。従って到達可能性は一方向的になり、\(u\) から \(v\) へは到達できるが、その逆は不可能という状況が自然に生じる。到達性の性質を議論する際は、グラフが有向か無向かで結論が変わりうる。
2 到達性の数学的性質
到達関係は、経路の存在をもとに定義されるため、到達性の論理的性質は「経路をどう連結できるか」に強く依存する。数学的には、到達関係を二項関係として捉え、反射性や推移性、対称性などの性質を分類する。
また到達集合は、この関係が具体的にどの頂点へ広がるかを表す。さらに強い連結性や弱い連結性のように、到達の向きや相互到達に着目して構造を整理する枠組みがある。
2.1 到達関係の性質
到達関係がどのような性質を満たすかは、経路の定義（有限長であること、端点の扱い等）と、グラフの種類（有向・無向）によって決まる。以下では代表的な性質を整理する。
2.1.1 推移性
推移性は、到達関係の中核となる性質である。具体的には、\(u\) から \(v\) へ到達でき、かつ \(v\) から \(w\) へ到達できるなら、\(u\) から \(w\) へも到達できることを意味する。
これは経路の連結によって説明できる。\(u\) から \(v\) までの経路と、\(v\) から \(w\) までの経路がそれぞれ存在すれば、途中の \(v\) を接続点として合わせることで、\(u\) から \(w\) までの有限経路が構成される。従って到達関係は推移的である。
2.1.2 反射性と対称性（ケース分け）
反射性は、任意の頂点 \(u\) について \(u\) から \(u\) へ到達可能であることを求める。経路の定義において「長さ 0 の経路」を許すなら、反射性は自明に成立する。長さ 0 を許さない流儀では定義が調整されるが、到達可能性の扱いとしては長さ 0 を許す形が一般的である。
対称性は、\(u\) から \(v\) へ到達できるなら \(v\) から \(u\) へも到達できることを要求する。無向グラフでは辺が双方向に移動可能なので対称性が成り立ちやすい。対して有向グラフでは向きのため一般に対称性は保証されないため、到達関係は対称的とは限らない。ここが有向・無向での重要な差である。
2.2 到達集合（到達ノード集合）
到達集合は、ある出発頂点 \(u\) に対して、\(u\) から到達可能な全頂点の集合として定義される。到達集合は到達関係を集合として具体化する概念であり、計算アルゴリズムでも直接扱われることが多い。
到達集合は、隣接関係を起点として反復的に広がる。まず \(u\) に隣接する頂点が候補となり、その候補からさらに一手進むことで新たな頂点が追加される。この拡張を停止できるのは、有限個の頂点しかないためであり、最終的に出発点から到達可能な範囲全体が集まる。
2.3 強い関係・弱い関係の整理
有向グラフでは、相互到達の有無によって到達に関する関係を二段階に整理できる。強い側面は、互いに行き来できるという条件に基づく。たとえば \(u\) から \(v\) へ到達でき、かつ \(v\) から \(u\) へも到達できる場合、両者の間には強い相互到達の性質があるといえる。
一方で弱い側面は、方向を無視したときの結びつきとして理解されることがある。すなわち、向きを無視すると同じ成分に含まれるか、という観点で分類する枠組みである。強い条件は相互到達に厳密に対応し、弱い条件はより広い範囲を一括りにしやすい。
3 代表的な到達判定アルゴリズム
到達可能性の判定は、経路の存在を直接列挙するのではなく、探索によって到達集合を構成し、目的地がその集合に含まれるかを確認する形で行うのが典型的である。探索は計算量の見積もりが容易であり、実装も一般化しやすい。
代表的な方法として深さ優先探索と幅優先探索が挙げられる。どちらも到達集合の構築に利用でき、到達判定にもそのまま適用可能である。
3.1 深さ優先探索による到達判定
深さ優先探索は、現在の頂点から出発して可能な限り深い方向へ進み、行き止まりに到達したら戻る方式で探索する。到達判定の文脈では、出発頂点から探索を開始し、到達可能な頂点を訪問済みとして管理しながら進める。
探索が終了した時点で、訪問済み集合に目的地 \(v\) が含まれていれば到達可能である。含まれていなければ、到達するための有限経路は存在しないことになる。深さ優先探索では再訪を避けるため、訪問フラグや既訪問集合を用意するのが基本である。
計算量は一般に、隣接リスト表現なら頂点数と辺数に比例する規模となる。無限ループを防ぐために訪問管理が重要であり、これにより探索は有限で停止する。
3.2 幅優先探索による到達判定
幅優先探索は、出発頂点からの距離（辺数）を段階的に広げる方式である。まず出発点から一手で到達できる頂点を列挙し、次に二手、三手…というように層状に進む。
到達判定では、探索中に目的地が現れた時点で到達可能と判断できる。全探索を行ってから判定してもよいが、目的地が近い場合には早期終了が有利になることがある。訪問管理は同様に必要であり、重複を抑えることで効率が保たれる。
幅優先探索は距離の最短性も関連して説明でき、探索の進み方が層構造を保つため、到達に必要な辺数の最小値を同時に把握する用途とも整合的である。
3.3 反復的・再帰的実装の違い
深さ優先探索は再帰関数で実装することも、明示的なスタックを用いて反復的に実装することも可能である。再帰的実装ではコードが簡潔になりやすい一方、深い探索で呼び出し回数が増えるため、実行環境のスタック制限に注意が必要になることがある。
反復的実装ではスタックを自前管理するため、制御の自由度が高く、大規模グラフでも安定して動かしやすい場合がある。幅優先探索は通常キューを用いた反復的実装が一般的であり、層状の展開に自然に対応する。
どちらの方式でも、到達集合を正しく構成するために訪問済み管理を徹底する点は共通である。実装上の違いは主にメモリの置き方と制御フローに現れる。
4 関連する概念と応用の見取り図
到達は他のグラフ概念と密接に結びつく。特に連結性や強連結性は、到達可能性を相互の観点や成分の観点でまとめたものとして捉えられる。さらに計算機科学では、状態遷移系の観点から「到達可能状態」の問題として応用されることが多い。
ここでは関連概念の整理と、状態遷移への接続を概観する。
4.1 到達と連結性（連結成分）
無向グラフでは、連結性は到達可能性の枠組みに一致しやすい。すなわち、ある頂点から別の頂点へ到達できるという関係が成り立つなら、それらは同一の連結成分に属する。
連結成分は、グラフ全体をいくつかのまとまりに分割する役割を持つ。各成分内では任意の二頂点が互いに到達可能であり、成分間では到達が不可能となる。これにより到達判定は、成分を調べることで効率的に答えられる場合がある。
4.2 到達と強連結性
有向グラフでは、強連結性は「互いに到達可能」という相互条件に基づく。すなわち、\(u\) から \(v\) へ到達でき、かつ \(v\) から \(u\) へも到達できる関係が成立する頂点群を、同一の強連結成分としてまとめる考え方がある。
強連結成分は、グラフを凝縮したときの構造理解にも役立つ。各成分を一点として扱うと、成分間の到達は方向を持ちつつ、全体としてはより単純な枠組みで整理できることが多い。強連結性は到達の向きが重要になる有向グラフにおいて特に意味を持つ。
4.3 応用例：状態遷移と到達可能状態
状態遷移の問題は、到達可能性を別の言葉で表したものとして理解できる。システムが取りうる状態を頂点、状態間の遷移を辺とすることで、特定の初期状態から到達可能な状態集合を求められる。
この枠組みは検証や設計支援の基礎にもなる。たとえば、ある操作列や入力の系列によって到達できる状態が存在するか、また危険状態へ到達してしまう可能性があるか、といった判定が到達性として表現される。到達集合を求める探索は、そのまま「到達可能状態の列挙」に対応する。
また、最短手数の概念が必要な場合には幅優先探索が適し、探索順序や記録方法を工夫すれば、到達経路の復元（前駆関係の追跡）にも拡張できる。