diff options
Diffstat (limited to 'tech-math/ws6.tex')
| -rw-r--r-- | tech-math/ws6.tex | 29 |
1 files changed, 29 insertions, 0 deletions
diff --git a/tech-math/ws6.tex b/tech-math/ws6.tex new file mode 100644 index 0000000..5042920 --- /dev/null +++ b/tech-math/ws6.tex @@ -0,0 +1,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 |