組合せ最適化

2章付近

クロスフリーとかラミナーとか後の方で使うっぽい話がされているけど、良く分からないので保留。木構造で表現できるのがクロスフリーで、DAGっぽくなるとクロスしちゃってるってことなんだろう、多分。(くらいのいい加減な認識。)

強連結成分の取得アルゴリズムについて。無向グラフなら辺があれば行って戻れるので、BFSなりDFSなりをすればすぐに取得できる。有向グラフについては、探索しても行けることしか分からないので、戻れることを別途調べないとダメ。戻れることを調べるには、辺の向きを逆向きにして探索する必要がある。

全部のノードについて、行って戻れる点を調べればいいが、それだと重たいので、強連結成分の数で抑えられるようにしたい。このためにできるだけ探索の結果を再利用したい。DFSで探索したときの根の方から優先的に戻れる点を探してやって、戻れる点(一つの強連結成分になる)を除去してやるとDFSの結果が木から森になる。この森の間で直接行ける点は存在しない。(除去されてしまった点を経由して行ける方法はあったかも知れないが、そうすると一緒の強連結成分に入っていないとおかしい。)なのでDFSするときに、木の上の方かどうかが判定できるような順番を適当に振ってやれば、この順番が同じ木に入るかどうかにも使える。DFSでstackからpopされた逆順に調べていくというのがうまくいく順番づけ(の一つだと思う)。