Exercise 2.7

算法设计与分析

Problem Discription

Let $H_n$ be $n$-dimension Hamming cube. For $i<n/2$ consider $L_i$ and $L_{n-i}$. Note that

$$|L_i|=\binom{n}{i}=\binom{n}{n-i}=L_{n-i}$$ so the $L_i$ and $L_{n-i}$ have the same size.

Show that there are $\binom{n}{i}$ paths

$$p_1,p_2,\cdots ,p_{\binom{n}{i}}$$ in $H_n$ such that
(i) each $p_i$ starts in $L_i$ and ends in $L_{n-i}$;
(ii) two different paths $p_i, p_j$ do not share any vertices.

Proof

Firstly, we simplify the problem:

• Set a source $S$ and build $\binom{n}{i}$ edges to $L_i$ with capacity of $1$.
• Set a sink $T$ and build $\binom{n}{i}$ edges from $L_{n-i}$ with capacity of $1$.
• Set a capacity of $1$ to each vertex.
• Make the undirected edges between $L_k$ and $L_{k+1}$ unidirected that points from $L_k$ to $L_{k+1}$, and set a capacity of $1$ to these edges.
• Now prove that the $maxflow$ of this network is $\binom{n}{i}$.

Secondly, we pick the bipartite graph between $L_k$ and $L_k+1$ out, where $k<n/2$. We determine the $maxmatchings$ of the bipartite graph we picked out.

• If $k+1>n/2$ i.e. $k+k+1=n$, then $$|L_k|=\binom{n}{k}=\binom{n}{n-k}=\binom{n}{k+1}=|L_{k+1}|$$ and there are $k+1$ edges from each vertex in $L_k$ to $L_{k+1}$. Obviously, the maxmatchings is $$|L_k|=\binom{n}{k}$$ .
• If $k<k+1<n/2$, then $$|L_k|=\binom{n}{k}<\binom{n}{k+1}=|L_{k+1}|$$ and there are $k+1$ edges from each vertex in $L_k$ to $L_{k+1}$. From Excercise 2.4, we could easily find out that the $maxmatching$ is $$|L_k|=\binom{n}{k}$$ .

Now we could get that the $maxflow$ from $L_k$ to $L_{k+1}$ is $\binom{n}{k}$.
Thirldy, according to the $Max\ Flow\ Min\ Cut\ Theory$, we could calculate the $maxflow$ of the graph:

$$val_{max}(f)=\min_{i\leqslant k<n/2}\left \{ \binom{n}{k}\right \}=\binom{n}{i}$$
Thus, there are $\binom{n}{i}$ paths satisfying that each $p_i$ starts in $L_i$ and ends in $L_{n-i}$ and two different paths $p_i, p_j$ do not share any vertices.