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

Soviet Rail Network

## 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 |$.

## 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.