グラフアルゴリズム
細かい話題を束ねた概念ページ。各節は元は独立ページだった。
最小全域木 (Minimum Spanning Tree)
グラフの全頂点を連結したまま辺の重み総和を最小化する木。連結性を保ちつつ冗長な辺を取り除く基本手法で、本ヴォルトでは stella のダンジョン生成における部屋接続（リージョン間グラフから余分な通路を除去）など実応用に用いられている。
アルゴリズム
- 無向グラフ
- Kruskal法 — 辺を重み昇順にソートし、閉路を作らない辺を Union-Find で貪欲に採用する
- Prim法 — 1頂点から始め、最小の隣接辺を逐次取り込む
- 有向グラフ
- Edmonds’ algorithm (Chu-Liu/Edmonds) — 有向グラフの最小全域有向木を求める。クラスカル法やプリム法を有向グラフに使っても有向木にならない（全域木にすらならない場合がある）ため専用アルゴリズムが必要
注意点
- 無向グラフの直感をそのまま有向グラフへ持ち込めない点が落とし穴。out-degree や強連結性を意識した別アルゴリズムが要る。
関連: graph-algorithms / data-structures / _moc-cs
強連結成分分解とトポロジカルソート
有向グラフの構造を解析する基盤アルゴリズム群。
強連結成分 (SCC)
有向グラフで任意の 2 頂点 について かつ の経路がある頂点同士を同じ成分にまとめる。強連結成分分解で各成分を 1 頂点に縮約 (condensation) すると DAG が得られる。
トポロジカルソート
DAG の頂点を、全ての辺が前方を向くように一列に並べる。依存関係の直列化に使い、巡回除去で DAG 化した後に適用するのが serigraph のパイプライン。
関連手法
- 木分解 (Tree Decomposition) — 木幅を定義してグラフを木にマッピングする。グラフの分割・近似に使う。
- PageRank — 遷移行列の定常状態でノードを重み付ける。グラフ上の重要度算出。
- 並列グラフ簡約 — プログラムを DAG として表現し各部分を並列評価する。データ競合が本質的にこの処理内に閉じるため、デッドロック等を意識せず並列実行できる。
関連: graph-algorithms / graph-algorithms / _moc-cs
Feedback Arc Set と巡回除去
有向グラフを DAG（有向非巡回グラフ）に変換するために「どの辺・頂点を取り除くか」を扱う一連の問題群。本ヴォルトでは serigraph（相互リンク文書をトポロジカルソートして PDF 化する自作ツール）の中核理論として深掘りされている。
関連する問題
- Feedback Arc Set (FAS) — 削除すると DAG が残る辺集合。各サイクルの少なくとも 1 辺を含む。
- Minimum Feedback Arc Set — どの辺を抜いてもサイズが減らない極小集合。集合内の辺は削除でなく 反転 しても Acyclic を保てる。できるだけ少ない辺で実現したいが NP困難なので近似解が提案されている。
- Feedback Vertex Set — 辺ではなく頂点を削除して巡回を断つ版。
- Maximum Acyclic Subgraph — 残す辺を最大化する双対的な定式化。NP困難。
- DAG vertex deletion — パス長を制約する頂点削除。UG-hard。
向き付けの等価性（タスク割当への応用）
論文 The Reduction of Directed Cyclic Graph for Task Assignment では、各頂点の out-degree を保つ向き付けは強連結成分が一致する（等価な orientation）ことを用い、巡回集合に沿った辺を反転して循環を消すアルゴリズムを示す。
serigraph の素朴アルゴリズム
- サイクルを探索し、各サイクル内で重み（被参照数）最小の 1 辺を削除
- サイクルが無くなるまで繰り返す
- トポロジカルソートして直列化
サイクル数が頂点数に対し指数的に増えるため遅く、MST や PageRank による重み付け、DFS で訪問順を木にする近似が検討されている。
関連: graph-algorithms / serigraph / _moc-cs