最大流/最小切断定理
たとえば東京都内から筑波に人が一斉に移動するというシチュエーションを考える。東京に核ミサイルが落ちてきて筑波にシェルターがあるとか。このとき何時間で避難可能か、という問題を解くには可能な東京から筑波への最大「流量」を求める必要がある。都内でいくら道路が広くても利根川あたりで橋が少なくて橋の交通量の合計が例えば車１００台/分だったらこれ以上の交通量が発生しないように都内で規制しないと渋滞になってしまう。ほかにボトルネックがない場合にはこの「車１００台/分」が求める最大流量となる。つまり出発点とゴールを分断する線をいろいろ引いてそれを横断する道路のキャパシティの合計を計算したとき、あらゆる線の引き方のうちでキャパシティが最小になる引き方のキャパシティ（最小切断）が最大の流量を与える。最大流を求める多項式時間のアルゴリズムが存在するので、逆に最小切断の問題は最大流の問題に置き換えて多項式時間で解くことが出来る。教科書見て実際に動くプログラム完成するも、いまだにそのアルゴリズムが何故うまくいくのか分からない。"preflow push"で検索すればどっかに解説あるから興味ある方はどんぞ。あるいは物理屋さんにはこの本とかいいかも。
