算法设计与分析笔记0x0A —— 网络流应用(1)

Soviet Rail Network
苏联到东欧的货最多能运多少
找到最小割,使得capacity之和最小(最少的炸药炸断)

Bipartite Matching

  • Goal: Maximize matching
  • Input: undirected, bipartite graph $G(L\cup R, E)$.
  • Matching: 每个节点只在一条边出现

Max Flow Formulation

  • Create digraph $G’=(L\cup R \cup {s,t},E’)$.
  • Direct all edges from L to R, and assign infinite (or unit) capacity.
  • Add source s, and unit capacity edges from s to each node in L.
  • Add sink t, and unit capacity edges from each node in R to t.

Theorem: Max cardinality matching in G = value of max flow in G’.

  • Pf. <=
    • Given max matching M of cardinality k.
    • Consider flow f that sends 1 unit along each of k paths.
    • f is a flow, and has cardinality k.
  • Pf. >=
    • Let f be a max flow in G’ of value k.
    • Integrality theorem => k is integral and can assume f is 0-1.
    • Consider M = set of edges from L to R with f(e) = 1.
      • each node in L and R participates in at most one edge in M
      • |M| = k: consider cut (L ∪ s, R ∪ t)

Perfect Matching

如果每个节点都正好被匹配一次(之前为最多被匹配一次)

S是一个节点集合, N(S)为所有与S中的点相邻的点
Observation 若一个二布图是完美匹配, |N(S)| >= |S|, for all S ⊆ L.

Marriage Theorem. G=(L ∪ R,E), |L|=|R|. 当且仅当 |N(S)| >= |S|, for all S ⊆ L, G存在完美匹配.

  • Pf.=> the previous observation
  • Pf.<= Suppose G does not have a perfect matching.
    • Formulate as a max flow problem and let (A, B) be min cut in G’.
    • Define $L_A = L \cap A$, $L_B = L \cap B$, $R_A = R \cap A$, $R_B = R \cap B$.
    • cap(A, B) = v(f*) = |M| < | L | (“<“: because no perfect matching)
    • Since min cut can’t use ∞ edges, no edge between $L_A$ and $R_B$
      • $cap(A, B) = | L_B | + | R_A |$
      • $N(L_A) \subseteq R_A$.
    • $|N(L_A)| \leq | R_A |$
      • $= cap(A, B) – | L_B |$
      • $< | L | – | L_B |$
      • $= | L_A |$.
    • This contradicts the condition

Disjoint Paths

  • Two paths are edge-disjoint if 可共享节点,不共享边
  • 每条边加上大小为1的capacity
  • Theorem: Max number edge-disjoint s-t paths equals max flow value.
    • Pf. <=
      • Suppose there are k edge-disjoint paths $P_1$, …, $P_k$.
      • Set f(e) = 1 if e participates in some path $P_i$; else set f(e) = 0.
      • Since paths are edge-disjoint, f is a flow of value k.
    • Pf. >=
      • Suppose max flow value is k.
      • Integrality theorem => there exists 0-1 flow f of value k.
      • Consider edge (s, u) with f(s, u) = 1.
        • by conservation, there exists an edge (u, v) with f(u, v) = 1
        • continue until reach t, always choosing a new edge
        • So we get a s-t path
      • Reduce the flow to 0 along the path, so we get a flow of value k-1
      • Repeat the process for k times, then we get k (not necessarily simple) edge-disjoint paths.

Network Connectivity

Given a digraph G = (V, E) and two nodes s and t, find min number of edges whose removal disconnects t from s.
A set of edges F ⊆ E disconnects t from s if all s-t paths uses at least on edge in F.
Theorem The max number of edge-disjoint s-t paths is equal to the min number of edges whose removal disconnects t from s.
Pf. <=

  • Suppose the removal of F ⊆ E disconnects t from s, and |F| = k.
  • All s-t paths use at least one edge of F. Hence, the number of edge- disjoint paths is at most k.

Pf. >=

  • Suppose max number of edge-disjoint paths is k.
  • Then max flow value is k.
  • Max-flow min-cut => cut (A, B) of capacity k.
  • Let F be set of edges going from A to B.
  • |F| = k and disconnects t from s.

Extensions to Max Flow

Node supply and demands d(v), v ∈ V.

  • demand if d(v) > 0; supply if d(v) < 0; transshipment if d(v) = 0

A circulation is a function that satisfies:

  • For each e, $0\leq f(e)\leq c(e)$
  • For each v, $\sum_{e\, in\, to\,v}f(e)-\sum_{e\, out\, of\,v}f(e)=d(v)$

Circulation problem given (V, E, c, d), does there exist a circulation?

Necessary condition: sum of supplies = sum of demands.
$$\sum_{v:d(v)>0}d(v)=\sum_{v:d(v)<0}-d(v)=:D$$

Max Flow Formulation

  • Add new source s and sink t.
  • For each v with d(v) < 0, add edge (s, v) with capacity -d(v).
  • For each v with d(v) > 0, add edge (v, t) with capacity d(v).
  • Claim: G has circulation iff G’ has max flow of value D.

Integrality theorem If all capacities and demands are integers, and there exists a circulation, then there exists one that is integer-valued.

Characterization Given (V, E, c, d), there does not exists a circulation iff there exists a node partition (A, B) such that $\sum_{v\in B}d_v>cap(A,B)$

Circulation with Demands and Lower Bounds

  • For each e ∈ E: $l(e)\leq f(e)\leq c(e)$
  • For each v ∈ V: $\sum_{e\, in\, to\,v}f(e)-\sum_{e\, out\, of\,v}f(e)=d(v)$

Circulation problem with lower bounds Given (V, E, l, c, d), does there exists a circulation?

  • Send l(e) units of flow along edge e.
  • Update demands of both endpoints.

Theorem There exists a circulation in G iff there exists a circulation in G’. If all demands, capacities, and lower bounds in G are integers, then there is a circulation in G that is integer-valued.

Survey Design

Survey design

  • Design survey asking $n_1$ consumers about $n_2$ products.
  • Can only survey consumer i about a product j if they own it.
  • Ask consumer i between $c_i$ and $c_i’$ questions.
  • Ask between $p_j$ and $p_j’$ consumers about product j.

Goal Design a survey that meets these specs, if possible.

Algorithm

  • Include an edge (i, j) if customer own product i.
  • Goal: find a flow that satisfies edge upper&lower bounds.

  • Formulate as a circulation problem with lower bounds.
    • Include an edge (i, j) if customer own product i.
    • Integer circulation <=> feasible survey design.

Leave a Reply

Your email address will not be published.