Exercise 3.1

算法设计与分析

Problem Discription

Design a polynomial-time algorithm for solving the following problem: Given an undirected Graph $G=(V,E)$ with degree constraints $c:V \rightarrow \mathbb{N}_0$, find a feasible orientation $H$ or determine that there is none. In particular:

1. Reduce it to a max flow problem. Prove that a max flow of a certain value can be converted into an orientation (and vice versa).

2. Redcuce it to a maximum matching. Show how certain matching can be converted into orientations (and vice versa).

Max Flow Algorithm

1. Note the undirected edges $(u,v) \in E$ as $e_{uv}$ and consider them as vertices of the max flow network.
2. Build an edge with $c=1$ from $S$ to each $E_{uv}$.
3. Build two edges with $c=1$ from each $E_{uv}$ to $u$ and $v$.
4. Build an edge from each $u \in V$ to $T$ with capacity of the constraint $c$.
5. Run $Max\ Flow$, and get the result $ans$.
6. If $ans=|E|$, there is a feasible orientation $H=(V,F)$ that
   $$(u,v) \in F\ \textrm{ iff }\ c(E_{u,v},v)=1$$
7. If $ans<|E|$, there is no feasible orientation.

Maximum Matching Algorithm

1. Note the undirected edges $(u,v) \in E$ as $e_{uv}$ and them on one side of matching.
2. For each $u\in V$, put $c$ vertices $u_1, u_2, ... , u_c$ on the other side of matching.
3. Build an edge from each $e_{uv}$ to $u_i$ and $v_i$.
4. Run $Maximum\ Matching$, and get the result $ans$.
5. If $ans=|E|$, there is a feasible orientation $H=(V,F)$ that
   $$(u,v) \in F\ \textrm{ iff }\ e_{uv}\ \textrm{and}\ v_i\ \textrm{is matched}$$
6. If $ans<|E|$, there is no feasible orientation.