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.

- Pf. <=

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