% -*- compile-command: "rubber -d --unsafe hw-03-graphs.tex" -*-
\documentclass[11pt]{tufte-handout}
\usepackage[num=3,date=September\ 20,topic=Graphs]{algorithms-hw}
\begin{document}
\coversheet
\begin{question}[5 points] \label{q:handshake}
Prove: for all $n \geq 1$, if $G$ is a connected graph with $n$
vertices and $n-1$ edges, then $G$ has no cycles. (This is the third
part of the proof from class, characterizing trees as having any two
out of three properties.)
\end{question}
\begin{question}[5 points] \label{q:connected-deg} Let $G=(V,E)$ be an
\marginnote{\emph{\ref{q:connected-deg}}\quad\qrcode{Think\
about\ cuts\ in\ the\ graph.\ A\ cut\ (S,T)\ is\ a\ partition\
of\ the\ vertices\ into\ two\ sets\ S\ and\ T\ such\ that\
every\ vertex\ is\ in\ either\ S\ or\ T\ but\ not\ both.}}
undirected graph with $n$ vertices, with no self-loops (that is, no
edges of the form $(v,v)$ from a vertex to itself). Show that if
every vertex has degree at least $n/2$, the graph is connected. If
it makes your proof easier, you may assume that $n$ is even.
\end{question}
\begin{question}[5 points]
Consider the family of undirected graphs $\mathcal{H}_k$ defined as
follows. $\mathcal{H}_k$ has $2^k$ vertices labelled with the
integers $0$ through $2^k - 1$. Vertices $u$ and $v$ are connected
by an edge if and only if the binary representations of $u$ and $v$
differ in exactly one bit position. For example, in $\mathcal{H}_4$, the
vertices $5$ and $13$ are connected by an edge since $5 = 0101_2$
and $13 = 1101_2$ differ in the first bit position, but the rest of
the bits are the same.
Consider doing a BFS in $\mathcal{H}_{10}$ starting at node $0$.
How many vertices are in $L_6$, that is, the sixth layer generated
by the BFS? Give your answer together with either a proof, or the
program you used to calculate the answer. Either approach will
receive full credit. (\emph{Hint} if you choose to write a program:
to flip the \verb|j|th bit of an integer \verb|n|, you can use
\verb|n ^ (1 << j)|, that is, the bitwise XOR of \verb|n| with the
result of shifting $1$ left \verb|j| times, that is, $2^{\texttt{j}}$. These
operators are valid in many languages such as Java, Python,
and C/C++.)
\end{question}
\begin{question}[10 points] \label{q:BFSQ} On the website you will
find a file called \texttt{graph.txt} which describes a large
undirected graph. The first line of the file contains a single
integer which is the number of edges in the graph. Each subsequent
line of the file describes one (undirected) edge, and contains two
space-separated strings which are the names of the two vertices at
the endpoints of the edge.
Write a program (in a programming language of your choice) to find a
shortest path from the vertex labelled with your first name to the
vertex labelled \texttt{END} (if there are multiple shortest paths
you can find any one of them). You should submit a text file
containing the list of vertices along this shortest path, starting
with your name and ending with \texttt{END}. Each vertex should be
on a separate line. For example, my solution looks like this:
\begin{verbatim}
Brent
7runq3
ajbkfy
ra17g1
jk9ojb
k289nn
gjinu8
END
\end{verbatim}
You should also turn in the code you used to find your path.
\end{question}
\end{document}