blob: 5042920af5fed61242a2906799189219a77dce6b (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
\def\pre#1{\leavevmode\llap{\hbox to \parindent{\hfil #1 \hfil}}}
\noindent {\bf Q1)} %#14:2
Considering a flow from Source $S$ which is connected to all members of $V_1$ and a similar sink $T$ with respect to $V_2$, this can be solved by the Ford-Fulkerson algorithm.
Let $V_{kj}$ be the $j^{th}$ member, from left to right of $V_k$. The optimum matching is $$\{V_11\to V_22, V_12\to V_27, V_13\to V_25, V_14\to V_21, V_15\to V_26, V_17\to V_24\}$$ because the Ford-Fulkerson algorithm halts, and Hall's theorem holds: there is a grouping of vertices in $V_1$ with a fewer number of neighbors than in the group.
\noindent {\bf Q2)} %#14:8
$w=3$.
Antichain: $\{x_1,x_2,x_3\}$.
Chain Partition: $\{x_3,x_4,x_5\}\cup\{x_6,x_1\}\cup\{x_2\}$.
\noindent {\bf Q3)} %#15:2
\let\sp\thinspace
$$\pi_1\pi_2 = \left({1\sp 2\sp 3\sp 4\sp 5\sp 6 \atop
3\sp 6\sp 4\sp 2\sp 1\sp 5}\right)$$
$$\pi_2\pi_1 = \left({1\sp 2\sp 3\sp 4\sp 5\sp 6 \atop
3\sp 1\sp 4\sp 5\sp 6\sp 2}\right)$$
$$\pi_3\pi_4 = \left({1\sp 2\sp 3\sp 4\sp 5\sp 6\sp 7\sp 8 \atop
1\sp 3\sp 8\sp 5\sp 7\sp 4\sp 6\sp 2}\right)$$
$$\pi_4\pi_3 = \left({1\sp 2\sp 3\sp 4\sp 5\sp 6\sp 7\sp 8 \atop
5\sp 4\sp 3\sp 6\sp 7\sp 8\sp 1\sp 2}\right)$$
\bye
|
