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