\documentclass[11pt]{article}
\usepackage{pictex, latexsym, graphicx,amsmath,amssymb,amsbsy,amsfonts,amsthm,verbatim}
\usepackage{fullpage}
\usepackage{etex}
\usepackage[all]{xypic}
\usepackage{lpic}
\usepackage{lscape}
\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 6
	
	\large Due Wednesday 12/04
	
	Assigned: 1, 4, 5, 7.
\end{center}


\textbf{1.} (\emph{Assigned!}) Prove that Prim's Algorithm produces a minimum-weight spanning tree. (\emph{Hint:} Use a proof format similar to the proof of Kruskal's Algorithm.)


\vspace{1em}

\textbf{2.} Consider the weighted graph with weighted adjacency matrix below (blank positions represent non-edges). Find a minimum-weight spanning tree.

\[
	\begin{bmatrix}
		   & 3 & 4 & 2 & 6 &   \\
	 	3 &    & 5 &    & 4 & 7 \\
		4 & 5 &    & 3 &    & 2 \\
		2 &    & 3 &    & 4 & 3 \\
		6 & 4 &    & 4 &    & 5 \\
		   & 7 & 2 & 3 & 5 &   
	\end{bmatrix}
\]

\vspace{1em}

\textbf{3.}  Consider the points below on the integer grid and the given non-optimal tour. 
Create an improved tour by following at least one iteration of the $\delta$-path algorithm.

\begin{center}
\includegraphics[height=2.5in]{hw6prob3.png}
\end{center}


\textbf{4.} (\emph{Assigned!}) Consider the weighted graph with weighted adjacency matrix below (blank positions represent non-edges). Compute all six 1-tree lower bounds on a minimum-weight traveling salesman tour.

\[
	\begin{bmatrix}
		   & 5 & 2 & 9 &    &   \\
	 	5 &    & 3 &    & 4 & 9 \\
		2 & 3 &    & 2 &    & 7  \\
		9 &    & 2 &    & 4 &    \\
		   & 4 &    & 4 &    & 8 \\
		   & 9 & 7 &    & 8 &   
	\end{bmatrix}
\]


\clearpage
\def\cI{\mathcal{I}}
\def\cM{\mathcal{M}}
\textbf{5.}  (\emph{Assigned!}) Let $G$ be a graph and let \[\cI = \{ J \subseteq E(G) : \text{each component of the subgraph with edges in $J$ contains at most one cycle}\}.\]
Prove that $(E(G), \cI)$ is a matroid.


\vspace{1em}
\textbf{6.}

\textbf{a.} Let $\cM = (S,\cI)$ be a matroid. Prove that the rank function is \emph{submodular}: that for all $A, B \subseteq S$ we have
\[
	r(A) + r(B) \geq r(A\cup B) + r(A \cap B).
\]
\textbf{b.} Prove that a function $r$ on the subsets of $S$ is the rank function of a matroid over $S$ if and only if it is submodular and also satisfies $r(\varnothing) = 0$ and $r(A \cup \{ x\}) \in\{ r(A), r(A) + 1\}$ for all $A \subset S$ and $x \in S \setminus A$. (\emph{Hint:} Construct a matroid $(S, \cI)$ where $\cI$ is defined using the rank function $r$.)


\vspace{1em}

\textbf{7.}  (\emph{Assigned!}) Present an implementation of the greedy algorithm that performs at most $|S|$ matroid queries of the type ``Is $A$ in $\cI$?''

\end{document} 