組合せ最適化(2-3)

2章から3章までを流し読み。というか眺めていたというか。移動中に読むような難易度の本ではないと思いつつ...。

基本的に定義とか定理とかの類が、数学的な用語で厳密に書き連ねられている部分。しかもかなり圧縮されているので...。昔授業で聞いたような話が難しく書いてあるという感じで、さらに発展的内容も書いてあった気がする。その辺りは必要になったらバックトラックすれば良さそうなのでほとんどスキップ。

アルゴリズム的な話で、メモしておく必要があるかも知れないものをメモ。他にもっと大事なものがあるだろうけれど、なんとなく重要というか、頭の中には入っていなかったもの。

有向グラフの連結成分取得

ある点集合に属する任意の二点間にパスが存在すれば、それが連結成分である。(無向グラフの場合だと単純にDFSなりBFSなりすれば連結成分が簡単に取得できる。)

まず、有向グラフ上の任意の点を開始点として、DFSをする。最初にバックトラックが発生した点から順に若い番号を振る。DFSが終了した時点で未到達の点から同様に、すべての点に到達するまで繰り返す。(要は森を帰りがけ順で番号を振るということ。)

有向グラフの各枝の向きを反転させる。番号が大きいものから順に、DFSを行う。到達できた点が連結成分であり、この操作をすべての点に到達するまで繰り返す。

後半のステップは、自分に到達する可能性のある点すべてを辿る操作で、自分より大きい番号の点は含まない。前半のステップから、自分より大きい番号の点とは自分から到達できない点であり、それを除いたものになっている。要は自分から到達可能な自分に到達可能な点の集合がこれにより得られる。つまりこの集合内のすべての点は、DFSの開始点に到達可能であり、そこから集合内の任意の点に到達可能である。これは連結成分の定義。