# グラフアルゴリズム ## 定義 グラフアルゴリズム(graph algorithms)とは、頂点と辺からなるグラフ $G=(V,E)$ を入力とし、探索・全域木・最短路・フローといった構造を求めるアルゴリズムの総称である。実行時間は頂点数 $|V|$ と辺数 $|E|$ の 2 変数で表され、隣接リストと隣接行列という 2 つの表現のどちらを選ぶかが、疎グラフと密グラフのいずれで有利かを決める。(Source: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 22 基本的グラフアルゴリズム]]) 大半のアルゴリズムは「不変式を保ちながら 1 ステップ進める」という共通の骨格を持つ。最短路では緩和(RELAX)、最小全域木では安全な辺の追加、最大フローでは増加道に沿ったフローの増加がそのステップにあたり、個々のアルゴリズムの違いはステップの選択順序に還元される。正当性は不変式の維持として証明され、実行時間は補助データ構造(優先度付きキュー・互いに素な集合族)の選択で決まる。 ## グラフの表現と探索 - **隣接リストは $\Theta(V+E)$ の記憶量で疎グラフに向き、隣接行列は $\Theta(V^2)$ で密グラフと辺の存在判定の $O(1)$ 化に向く。** この選択は最短路問題にも波及し、全点対最短路では隣接行列を前提とする Floyd-Warshall と、疎グラフ向けの Johnson が対置される。 - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 22 基本的グラフアルゴリズム]] - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 25 全点対最短路]] — Floyd-Warshall の $\Theta(V^3)$ 対 Johnson の $O(V^2\lg V + VE)$ - **BFS は辺の重みを持たないグラフの最短路距離を与え、DFS は発見時刻と終了時刻という時刻印を通じてグラフの構造を暴く。** 括弧定理・白色路定理・辺の 4 分類(木辺・後退辺・前進辺・横断辺)が DFS の解析基盤である。 - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 22 基本的グラフアルゴリズム]] — 定理 22.7・22.9 - **DFS の時刻印から、トポロジカルソートと強連結成分分解がいずれも $\Theta(V+E)$ で導かれる。** 有向グラフの非巡回性は「DFS が後退辺を持たない」ことと同値である。 - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 22 基本的グラフアルゴリズム]] ## 不変式を保つ 1 ステップという共通骨格 - **最短路アルゴリズムは INITIALIZE-SINGLE-SOURCE と RELAX を共有し、緩和の順序と回数だけが異なる。** Bellman-Ford は全辺を $|V|-1$ 回、DAG-SHORTEST-PATHS はトポロジカル順に 1 回、Dijkstra は距離推定の最小の頂点から順に緩和する。 - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 24 単一始点最短路問題]] — §24.5 の三角不等式・上界性質・収束性質・経路緩和性質が共通の正当性基盤 - 留保: Bellman-Ford は負辺を許し負閉路も検出するが、Dijkstra は非負辺を前提とする貪欲アルゴリズムである - **最小全域木は「安全な辺を 1 本ずつ加える」という一般法 GENERIC-MST に還元され、Kruskal と Prim はその 2 つの具体化にすぎない。** 定理 23.1(カットを尊重する軽い辺は安全)が正当性を与える。 - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 23 最小全域木]] - **最大フローは残余ネットワーク上の増加道でフローを増やす Ford-Fulkerson 法に還元され、最大フロー最小切断定理(定理 26.6)が停止時の最適性を保証する。** プッシュ再ラベル法は増加道を使わない別系統として対置される。 - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 26 最大フロー]] — EDMONDS-KARP の $O(VE^2)$、GENERIC-PUSH-RELABEL の $O(V^2E)$、RELABEL-TO-FRONT の $O(V^3)$ ## 補助データ構造による計算量の決定 - **同じアルゴリズムでも、優先度付きキューの実現方式が漸近計算量を変える。** Prim は 2 分ヒープで $O(E\lg V)$、フィボナッチヒープで $O(E + V\lg V)$、Dijkstra も同様に $O(V^2)$ から $O(V\lg V + E)$ まで変わる。 - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 23 最小全域木]] / [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 24 単一始点最短路問題]] - 関連: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 19 フィボナッチヒープ]] — DECREASE-KEY のならし $O(1)$ がこの改善の源 - **Kruskal は互いに素な集合族を使い、その $O(m\,\alpha(n))$ が辺のソート $O(E\lg E)$ に吸収されて全体が $O(E\lg V)$ になる。** - 根拠: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 21 互いに素な集合族のためのデータ構造]] ## 未解決の問い - 緩和・安全な辺・増加道は同型の骨格を持つが、本書はこれらを統一する抽象を明示的には立てていない。3 者を包む一般的な枠組み(マトロイド、劣モジュラ性など)はどこまで整備されているか。 - 隣接リストと隣接行列の選択は疎密で決まるとされるが、実機ではキャッシュ局所性が支配的なことがある。表現の選択基準に記憶階層を織り込む理論はあるか。 - 最大フローの計算量は Ford-Fulkerson 系(増加道)とプッシュ再ラベル系で異なる進化を遂げたが、両系統を統一的に説明する枠組みはあるか。 ## 未編纂の観察 - **グラフ問題は線形計画法の特殊ケースとして再定式化でき、双対性がグラフ側の定理と対応する。** 第 29 章 §29.2 は単一始点最短路・最大フロー・最小費用フロー・多品種フローをいずれも多項式サイズの線形計画として定式化し、§29.4 は最大フロー最小切断定理を双対性の具体例として明示的に参照する。すなわち第 24・26 章がグラフ固有の議論として構築した定理群は、より一般的な最適化理論の中に位置づけ直すことができる。ただし専用アルゴリズムのほうが実行時間は小さい。(Source: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 29 線形計画法]], [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 26 最大フロー]], [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 24 単一始点最短路問題]]) - **差分制約式系という非グラフ問題が制約グラフ上の最短路に帰着し、実行可能解の存在が負閉路の非存在と同値になる。** 第 24 章 §24.4 のこの帰着は、グラフアルゴリズムが「グラフとして与えられた問題」だけでなく「グラフに翻訳できる問題」の道具でもあることを示す。同じ構図は第 26 章の 2 部グラフ最大マッチングにも現れ、そこではマッチング問題がフローネットワークに翻訳されて整数性定理により整数解が保証される。(Source: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 24 単一始点最短路問題]], [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 26 最大フロー]]) - **全点対最短路は動的計画法とグラフ探索の 2 系統で解け、疎密がその選択を決める。** 第 25 章の Floyd-Warshall は中間頂点集合を拡大する漸化式による動的計画法(第 15 章の技法)で $\Theta(V^3)$、Johnson は Bellman-Ford による再重み付けを前処理として Dijkstra を $|V|$ 回走らせる構成で $O(V^2\lg V + VE)$ を得る。同じ問題に対して第 IV 部の設計技法と第 VI 部の専用アルゴリズムが競合し、入力の密度で優劣が入れ替わる。(Source: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 25 全点対最短路]], [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 15 動的計画法]]) - **NP 完全問題の多くがグラフ上の問題であり、グラフアルゴリズムの多項式時間の世界と隣接している。** CLIQUE・VERTEX-COVER・HAM-CYCLE・TSP はいずれもグラフ問題であり、第 22〜26 章が多項式時間で解いた問題群のすぐ隣にある。最短路(多項式時間)とハミルトン閉路(NP 完全)、最小全域木(多項式時間)と最小シュタイナー木(NP 困難)のように、定義のわずかな違いが計算量の断層をまたぐ。(Source: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 34 NP完全性]], [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 22 基本的グラフアルゴリズム]]) ## 関連 - 書籍: [[アルゴリズムイントロダクション 第3版]] - 概念: [[アルゴリズム設計技法]] / [[計算複雑性]] ## 出典 - T. コルメン, C. ライザーソン, R. リベスト, C. シュタイン 共著, 『アルゴリズムイントロダクション 第3版 総合版』, 近代科学社, 2013, 第 15・19・21・22・23・24・25・26・29・34 章.