\documentclass[11pt]{article}
\usepackage{header}
%%% Change these %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def
\title{HW 3}
\def
\due{Friday, September 16 at 10PM}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\tikzset{main node/.style={circle,fill=blue!20,draw,minimum size=1cm,inner sep=0pt},
}
\begin{document}
\maketitle
\fontsize{12}{15}
\selectfont
\newcommand{\findtour}{\textsc{FindTour}}
\newcommand{\findeuleriantour}{\textsc{FindEulerianTour}}
\newcommand{\splice}{\textsc{Splice}}
\begin{Questions}
\Question{\bf Sundry}
Before you start your homework, write down your team. Who else did you work with on this homework? List names and email addresses. (In case of hw party, you can also just describe the group.) How did you work on this homework? Working in groups of 3-5 will earn credit for your "Sundry" grade.
%%% Include questions here %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Question (30 points)
\textbf{CalCentral}
\\
%From sp14
Let's consider the new course enrollment platform. We are given $n$ students and $m$ discussion sections.
Each discussion section $u$ has some number, $q_u$ of seats,
and we assume that the total number of students is larger than the total number of seats
(i.e. $
\sum_{u=1}
^m
{q_u}
< n$).
Each student ranks the $m$ discussion sections in order of preference, and the instructor for each discussion ranks the $n$ students.
Our goal is to find an assignment of students to seats (one student per seat) that is
\textit{stable}
in the following sense:
\begin{itemize}
\item There is no student-section pair $(s,u)$ such that $s$ prefers $u$ to her allocated discussion section
and the instructor for $u$ prefers $s$ to one of the students assigned to $u$.
(This is like the stability criterion for Stable Marriage:
it says there is no student-section pair that would like to change the assignment.)
\item There is no discussion section $u$ for which the instructor prefers some unassigned student $s$ to one of the students assigned to $u$.
(This extends the stability criterion to take account of the fact that
some students are not assigned to discussions.)
\end{itemize}
Note that this problem is almost the same as the Stable Marriage Problem, with two differences:
(i) there are more students than seats; and
(ii) each discussion section can have more than one seat.
\begin{Parts}
\Part (10 points) Explain how to modify the propose-and-reject algorithm so that
it finds a stable assignment of students to seats.
(Hint: What roles of students/instructors will be in the propose-and-reject algorithm? What does "women have men on a string" mean in this setting?)
\Part (10 points) State a version of the Improvement Lemma (see Lecture Note 4)
that applies to your algorithm, and prove that it holds.
\Part (10 points) Use your Improvement Lemma to give a proof that your algorithm terminates, that every seat is filled, and that the assignment your algorithm returns is stable.
\end{Parts}
\Question (27 points)
\textbf{Graph Basics}
In the first few parts, you will be answering questions on the following graph $G$.
\begin{figure}[h]
\centering
\includegraphics[width=8cm]{resources/simple_graph.png}
\end{figure}
\begin{Parts}
\Part (3 points) What are the vertex and edge sets $V$ and $E$ for graph $G$?
\Part (3 points) Which vertex has the highest in-degree? Which vertex has the lowest in-degree? Which vertices have the same in-degree and out-degree?
\Part (3 points) What are the paths from vertex $B$ to $F$, assuming no vertex is visited twice? Which one is the shortest path?
\Part (3 points) Which one(s) of the followings is a cycle in $G$?
\begin{enumerate}
\item
\{
$(B,C)$, $(C,D)$, $(D,B)$
\}
\item
\{
$(F,G)$, $(G,F)$
\}
\item
\{
$(A,B)$, $(B,C)$, $(C,D)$, $(D,B)$
\}
\item
\{
$(B,C)$, $(C,D)$, $(D,H)$, $(H,G)$, $(G,F)$, $(F,E)$, $(E,D)$, $(D,B)$
\}
\end{enumerate}
\Part (3 points) Which one(s) of the followings is a walk in $G$?
\begin{enumerate}
\item
\{
$(E,G)$
\}
\item
\{
$(E,G)$, $(G,F)$
\}
\item
\{
$(F,G)$, $(G,F)$
\}
\item
\{
$(A,B)$, $(B,C)$, $(C,D)$
\}
\item
\{
$(E,G)$, $(G,F)$, $(F,G)$, $(G,F)$
\}
\item
\{
$(E,D)$, $(D,B)$, $(B,E)$, $(E,D)$, $(D,H)$, $(H,G)$, $(G,F)$
\}
\end{enumerate}
\Part (3 points) Which one(s) of the followings is a tour in $G$?
\begin{enumerate}
\item
\{
$(E,G)$
\}
\item
\{
$(E,G)$, $(G,F)$
\}
\item
\{
$(F,G)$, $(G,F)$
\}
\item
\{
$(A,B)$, $(B,C)$, $(C,D)$
\}
\item
\{
$(E,G)$, $(G,F)$, $(F,G)$, $(G,F)$
\}
\item
\{
$(E,D)$, $(D,B)$, $(B,E)$, $(E,D)$, $(D,H)$, $(H,G)$, $(G,F)$
\}
\end{enumerate}
\textbf{In the following three parts, let's consider a general undirected graph $G$ with $n$ vertices ($n \geq 3$).}
\Part (3 points) True/False: If each vertex of $G$ has degree at most 1, then $G$ does not have a cycle.
\Part (3 points) True/False: If each vertex of $G$ has degree at least 2, then $G$ has a cycle.
\Part (3 points) True/False: If each vertex of $G$ has degree at most 2, then G is not connected.
\end{Parts}
\Question (20 points)
\textbf{Edge complement}
\begin{figure}[!h]
\centering
\includegraphics[width=0.8\textwidth]{resources/S2.png}
\end{figure}
The
\textbf{edge complement}
graph of a graph $G = (V,E)$ is a graph $G' = (V',E')$, such that $V' = E$, and $(i,j)
\in{\{i,j\}} E'$ if and only if $i$ and $j$ had a common vertex in $G$. In the above picture, the graph on the right is the edge complement of the graph on the left: for every edge $e_
$ in the graph on the left there is a vertex in the graph on the right. If two edges $e_
{\{i,j\}}
$ and $e_
{\{j,k\}}
$ share a vertex $j$ on the left, then the corresponding vertices on the right have an edge $j$ connecting them.
\begin{Parts}
\Part (10 points) Prove or disprove: if a graph $G$ has an Eulerian tour, then its
\textbf{edge complement}
graph has an Eulerian tour.
\Part (10 points) Prove or disprove: if a graph's
\textbf{edge complement}
graph $G'$ has an Eulerian tour, then graph $G$ has an Eulerian tour.
\end{Parts}
\Question (20 points)
\textbf{Proof in Graph}
Please prove or disprove the following claims.
\begin{Parts}
\Part (10 points) Suppose we have $n$ websites such that for every pair of websites $A$ and $B$,
either $A$ has a link to $B$ or $B$ has a link to $A$. Prove or disprove that
there exists a website that is reachable from every other website by clicking at
most 2 links. (
\textit{Hint: Induction}
)
\Part (10 points)
In the lecture, we have shown that a connected undirected graph has an Eulerian tour if and only if every vertex has even degree.
Prove or disprove that if a connected graph $G$ on $n$ vertices has exactly $2d$ vertices of
odd degree, then there are $d$ walks ($d>0$) that
\emph{together}
cover all the edges of
$G$ (i.e., each edge of $G$ occurs in exactly one of the $d$ walks; and each of
the walks should not contain any particular edge more than once).
%
%
\Part (8 points)
%An alternative type of tour to Euler Tour in graph is a Rudrata
%Tour: a tour that visits every vertex exactly once. Prove or disprove that the
%hypercube contains a Rudrata cycle, for hypercubes of dimension $n
\geq
%2$.
%
%
\end{Parts}
\Question (20 points)
\textbf{Touring Hypercube}
In the lecture, you have seen that if $G$ is a hypercube of dimension $n$, then
\begin{itemize}
\item The vertices of $G$ are the binary strings of length $n$.
\item $u$ and $v$ are connected by an edge if they differ in exactly one location.
\end{itemize}
A
\emph{Hamiltonian tour}
of a graph is a sequence of vertices
$v_0, v_1,
\ldots, v_k$ such that:
\begin{itemize}
\item Each vertex appears exactly once in the sequence.
\item Each pair of consecutive vertices is connected by an edge.
\item $v_0$ and $v_k$ are connected by an edge.
\end{itemize}
\begin{Parts}
\Part (10 points) Show that the hypercube has an Eulerian tour if and only if $n$ is even.
\Part (10 points) Show that the hypercube has a Hamiltonian tour.
\end{Parts}
\Question (15 points)
\textbf{Edge Colorings}
An edge coloring of a graph is an assignment of colors to edges in a graph where any two edges incident to the same vertex have different colors. An example is shown on the left.
\begin{figure}[h]
\centering
\includegraphics[width=8cm]{resources/coloring_edges.png}
\end{figure}
\begin{Parts}
\Part (3 points) Show that the 4 vertex complete graph below can be 3 edge colored (use the numbers $1,2,3$ for colors. A figure is shown on the right.)
\Part (3 points) How many colors are required to edge color a 3
dimensional hypercube?
\Part (3 points)
Prove that any graph with maximum degree $d$ can be edge colored
with $2d-1$ colors.
\Part (3 points)
Show that any tree has a degree $1$ vertex.
(You may use any definition of a tree that we provided in the notes, homeworks
or lectures to prove this fact.)
\Part (3 points)
Show that a tree can be edge colored with $d$ colors where $d$ is the maximum
degree of any vertex.
\end{Parts}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{Questions}
\end{document}