\documentclass[11pt]{article}
\usepackage{pictex, latexsym, graphicx,amsmath,amssymb,amsbsy,amsfonts,amsthm,verbatim}
\usepackage{fullpage}
\usepackage{etex}
\usepackage[all]{xypic}
\usepackage{lpic}
\setlength{\parindent}{0em}

\def\vx{\mathbf{x}}
\def\vc{\mathbf{c}}
\def\vb{\mathbf{b}}
\def\vy{\mathbf{y}}

\begin{document}

\thispagestyle{empty}



\begin{center}
	\Large\bf MATH 482, Spring 2013 - Homework 4
	
	\large Assigned Monday 10/07. Due Wednesday 10/09.
	
	Assigned: 1.e, 2.d, 3.b, 4.a.
\end{center}

\textbf{1.} Find a maximum-weight perfect matching and a minimum-weight vertex cover for the bipartite graphs with weight matrices given below. (\emph{Assigned: e})
\begin{center}
\begin{tabular}[h]{c@{\qquad}c@{\qquad}c}
$\begin{bmatrix}
 6  &  8  &  6  &  3 \\
 3  &  9  &  9  &  7 \\
 5  &  0  &  4  &  1 \\
 0  &  3  &  9  &  7 
\end{bmatrix}$
&
$\begin{bmatrix}
 3  &  1  &  8  &  5  &  9 \\
 8  &  5  &  1  &  5  &  8 \\
 5  &  6  &  2  &  7  &  1 \\
 3  &  4  &  2  &  3  &  6 \\
 8  &  8  &  3  &  9  &  8 
\end{bmatrix}$
&
$\begin{bmatrix}
 5  &  7  &  3  &  8  &  0 \\
 4  &  9  &  5  &  8  &  4 \\
 1  &  8  &  9  &  1  &  9 \\
 1  &  7  &  2  &  8  &  2 \\
 9  &  6  &  1  &  1  &  6 
\end{bmatrix}$
\\
\textbf{a.} &
\textbf{b.} &
\textbf{c.} \\
$\begin{bmatrix}
 6  &  4  &  4  &  4  &  9  &  9 \\
 5  &  9  &  2  &  1  &  4  &  7 \\
 1  &  0  &  9  &  6  &  3  &  9 \\
 9  &  5  &  4  &  6  &  7  &  9 \\
 5  &  8  &  5  &  1  &  4  &  9 \\
 5  &  5  &  8  &  9  &  7  &  8 
\end{bmatrix}$
&
$\begin{bmatrix}
 8  &  1  &  3  &  9  &  4  &  3 \\
 3  &  9  &  0  &  8  &  8  &  4 \\
 9  &  1  &  4  &  1  &  0  &  0 \\
 8  &  3  &  5  &  8  &  6  &  1 \\
 6  &  1  &  0  &  0  &  5  &  0 \\
 2  &  1  &  0  &  7  &  0  &  9 
\end{bmatrix}$
&
$\begin{bmatrix}
 6  &  3  &  4  &  4  &  1  &  6 \\
 7  &  2  &  8  &  7  &  5  &  9 \\
 2  &  7  &  3  &  3  &  2  &  1 \\
 9  &  0  &  1  &  0  &  7  &  8 \\
 7  &  0  &  0  &  6  &  6  &  5 \\
 9  &  6  &  9  &  6  &  7  &  6 
\end{bmatrix}$
\\
\textbf{d.} &
\textbf{e.} &
\textbf{f.} 
\end{tabular}
\end{center}

\textbf{2.} Find a minimum-weight perfect matching and a maximum-weight vertex under-cover for the bipartite graphs with weight matrices given above. (\emph{Assigned: d})

\vspace{1em}

\textbf{3.} In the graphs below, perform the blossom algorithm with the given matchings to either find a perfect matching or a set $A$ such that $\operatorname{oc}(G-A) > |A|$.

\begin{center}
\begin{tabular}[h]{c@{\quad}c}
\includegraphics[width=0.35\textwidth]{blossomproba}
&
\includegraphics[width=0.55\textwidth]{blossomprobb}\\
\textbf{a.} & \textbf{b.} (\emph{Assigned!})\\
(Use a tree rooted at $x$ for this problem.)  &
\end{tabular}
\end{center}

\clearpage
\textbf{4.} Let $X$ and $Y$ be sets of size $n$ where every element $x \in X$ has a total ranking of the elements of $Y$, and every $y \in Y$ has a total ranking of the elements of $X$.
Let $M$ be a stable matching found by the Gale-Shapely proposal algorithm with the elements of $X$ proposing, and let $M'$ be any stable matching.\\
\textbf{a.} (\emph{Assigned!}) Prove that for every $x \in X$, $x$ prefers its match in $M$ to its match in $M'$.\\
\textbf{b.} Prove that for every $y \in Y$, $y$ prefers its match in $M'$ to its match in $M$.\\


\textbf{5.} Find stable matchings for the rankings below.

\begin{center}
	\begin{tabular}[h]{c@{\quad}c@{\qquad}c@{\quad}c}
	& &								 	$h : p > q > r > s > t$ & 	$p : i > j > \ell > k > h$\\
	$a : x > y > z > w$ & $w : a > b > d > c$ & 	$i : p > s > q > t > r$ & 	$q : j > i > h > k > \ell$\\
	$b : x > y > w > z$ & $x : c > d > b > a$ & 		$j : r > s > t > q > p$ & 	$r : i > \ell > k > j > h$\\
	$c : w > y > z > x$ & $y : d > c > b > a$ & 		$k : p > r > t > s > q$ & 	$s : k > j > \ell > h > i$\\
	$d : x > w > z > y$ & $z : a > d > c > b$ & 		$\ell : q > r > p > t > s$ & 	$t : h > i > k > j > \ell$\\
	\multicolumn{2}{c}{\textbf{a.}} & \multicolumn{2}{c}{\textbf{b.}}
	\end{tabular}
\end{center}


\end{document} 