グラフ理論のかるい復習

CS

グラフ理論が苦手な気がしてきたのでさっと組み合わせ最適化をおさらいすることにした．
実はDinicとか強連結成分分解とか今まで1回も書いたことないのでそろそろ書いておいた方がいい気がしてきた．

2章 グラフ

  • 定義がいっぱい
  • 命題2.2

グラフG，X⊆V(G)に対し，以下のa,b,cは互いに同値．
a. XはGの頂点被覆．
b. V(G)-X はGの安定集合(どの2点もつながってない頂点集合)．
c. V(G)-X はGの補グラフのクリーク(部分的な完全グラフ)．

  • 頂点被覆問題はNP-Complete，最小頂点被覆問題はNP-Hardであるとされる．
  • 森：無閉路なグラフ，木：連結な森
  • 木：いい性質がいっぱい(略)
  • 強連結：有向グラフにおいて，∀a,b∈V(G)に対しa->b，b->aのパスがある
  • 強連結成分：ふつうのグラフを↑の条件で同値類に分解したもの
    • dfs2回使って線形時間で求められる．実装には逆グラフが必要になるので注意．
    • トポロジカルソートしてやって，それを逆からたどる… という感じ．
  • 無閉路な有向グラフ(DAG)：トポロジカルソートできる
  • 耳：グラフをいくつかのパスと閉路に分解
    • 2連結(グラフからどの1点を除去しても連結) ⇔ 耳分解が1つの閉路といくつかの耳からなる(プロパーな耳分解)
  • 2部グラフ：頂点集合が左と右に分かれる
    • 2部グラフ⇔奇数長閉路がない

6章 全域木

  • 最大重み森問題と最小全点木問題は等価
    • グラフをちょっとだけいじって，辺の重みの符号を反転させると帰着できる．
  • 頂点数nの完全グラフに対する全域木はn^{n-2}通りある．
  • Kruskal: UnionFind使ってO(MlogN)．
  • Prim: ふつうのヒープを使ってO(MlogN)．フィボナッチヒープを使うともうちょい速くなるらし．

7章 最短パス

  • グラフがConservative: 負閉路が存在しない
  • 最短パスに関するアルゴリズムには，いずれも最適性原理が背後にあると考えていい．つまり，d(v,w)がv->wへの最短路であるとき，d(v,w)=min(u:wの隣接辺) d(v,u)+d(u,w) であるということが前提にある．(c.f.ICPC2010 Domestic Problem E)
  • Dijkstra: 普通のヒープでO(MlogN)．(なんかよく忘れてしまう)
  • Moore-Bellman-Ford: 1点から全点への最短パス．ぐるぐるやるだけ．
REP(i,N) L[i]=INFTY;
L[s]=0;
REP(i,N) FOREACH((v,w),edge) L[w]=min(L[w],L[v]+c[v][w]);
    • これは，負閉路がないならば，最短パスはN本以下の辺を通っていけるということに基づく．
    • 計算量は明らかにO(NM)．たまに使うのだけどこれもなぜかよく忘れる．
    • Bellman-Ford は負閉路の検出にも使える．(負閉路があるならN回ループしたあともなおどこか更新されるところがあるはずなので…)
  • Floyd-Warshall: 超シンプル
    • REP(k,N) REP(i,N) REP(j,N) L[i][j]=min(L[i][j],L[i][k]+L[k][j]);

8章 最大流

  • 最大流=最小カット
    • 流せる最大の量は，グラフのボトルネックに等しい，という定理．理論的には，残容量グラフのソースから到達可能な部分とか考えればよかったはず．
  • Ford-Furkerson: フローが最大流 ⇔ 残容量グラフでs-tパスが存在しない という事実を使って，とにかく流しまくるというもの．
  • 系8.7:

ネットワークの容量が全て整数なら，最大流量も整数．

    • Ford-Furkersonアルゴリズムの正当性とその手法から直ちにいえるんだけど，なんか不思議な感じもしなくもない．
    • まぁ，フローの総量が9.12とかになっていたら，容量が全部整数だからどっか中途半端に使ってないところに流して総量を10以上の整数値にできるもんねぇ．というもの．
  • Mengerの定理:

グラフにおいて，K本の，2点s,tを結ぶ互いに辺素なパスが存在する ⇔ どのK-1本の辺を除いてもs-tパスが存在する

    • ここで，K本の〜… というのは，長さKのパスと言う意味ではなく，辺で互いに交差しないようなパスがK本ある，ということであるのに注意．
    • 必要性は明らか．十分性は，K-1本の辺を除いてもパスがある→最小カットはK以上である より，流量K以上のs-tパスがあることから従う．
    • 「辺素」を「点素」に変えても同じことが従う．
  • Edmonds-Karp:
    • Ford-FurkersonでBFSを使うようにしたもの．O(M^2N)．
  • Dinic:
    • O(MN^2)．経験的にとても速いことが知られている．
    • レベルグラフを構築し，ブロックフローを流していく．