Flows (Grpah Theory, Chapter 6)

  • 辺を2方向の向きで区別するため,e=xy の時,f(e, x, y) と f(e, y, x) という書き方をする

Circulations

  • circulation:f(e, x, y) = -f(e, y, x) で f(v, V) = 0
  • bridge なら流量 0

Flows in networks

  • network:グラフ+capacity function, flow:始点終点 s, t
  • min-cut max-flow 定理
    • max-flow なら増大路がない,で証明すると簡単

Group-valued flows

  • (Tutte) 多項式 P で以下のようなもの存在:有限群 H. H-flow の数は P(|H| - 1)

Flow number

  • k-flow:全辺の流量が 0<|f(e)|
  • flow number:グラフに k-flow が存在する最小の k
  • 2-flow 存在 ⇔ 全点次数 2
  • 3-flow 存在 かつ cubic ⇔ bipartite