グラフ典型
総合
ある状態$ s\in Sがあるときは、頂点を$ |S|倍する
ある点から全ての点→全ての点からある点の言い換え: 辺を逆向きにする
なもりグラフのサイクルは次数$ 1の頂点を削除していくと求められる
ある推移的な関係$ u \le vが矛盾していないことを確かめるには、関係でグラフを構築して強連結成分がなければOK
辺の本数の削減
集合$ X, Yに対して、$ Xに含まれる点すべてから$ Yに含まれる点すべてにパスがあってほしいときは、頂点$ sを用意して$ x\in X, y \in Yにたいして$ x \to s, s \to yとすると辺の本数を$ O(|X|+|Y|)に抑えられる
$ u\to v, u\to w, v\to wみたいな推移的な関係を表したいときは、$ u \to v, v \to wのように隣り合う頂点のみをつなぐことで辺の数を削減できることがある
二部グラフの最小点被覆、最大安定集合 (最大独立集合)、最小辺被覆は二部マッチングで求まる
Dilworthの定理
DAGの最小パス被覆 (DAG-MSCP) は二部マッチングで求まる
辺が推移的なDAGの最大安定集合(最大独立集合)の反鎖 (antichain) は二部マッチングで求まる
最小全域木
最大全域木もできる: 辺のコストを$ -1倍
最短路
ダイクストラの距離は和じゃなくても$ x * y \ge xかつ$ x * y \ge y(≒三角不等式を満たす)ならOK
最大流
$ s, t をソース、シンクとする。
ソースやシンクが複数ある場合
0. ソースを$ s_1, \ldots, s_n、シンクを$ t_1, \ldots, t_mとする
1. 頂点$ s^*, t^*を作り新たなソース、シンクとする
2. 辺$ s^* \to s_i(容量$ \infty)と辺$ t_i \to t^*(容量$ \infty)を張る
容量に上下限がある場合
1. 頂点$ s^*, t^*を作り新たなソース、シンクとする
2. 上下限がある全ての辺$ u \to v(容量$ \lbrack low, high \rbrack)について
1. 容量を$ high - lowにする
2. 辺$ s^* \to v, u \to t^*(どちらも容量$ low)を追加する
3. 辺$ t \to s(容量$ \infty)を追加する
4. $ s^*から$ t^*へフローを流す
$ s^*から出る辺や$ t^*へ入る辺に$ \text{流量}\neq\text{容量}なものがある場合、上下限の制約が矛盾している(infeasible)
頂点に容量がある場合
1. 頂点$ v(容量$ c)を頂点$ v_1と頂点$ v_2に分割する
$ vに入る辺はすべて$ v_1に入るようにする
$ vから出る辺はすべて$ v_2から出るようにする
2. 辺$ v_1 \to v_2(容量$ c)を張る
最小費用流