
For example, suppose you had just invented the complete binary tree.
Let's first consider the permutation routing problem where the packet
originating at input $i$ is requested by output $i$.  (This is the
routing problem corresponding to the identity permutation, where
$\pi(i) = i$ for all $i$.)  This is a pretty easy problem; if you
route packets in the way described above, then at most one packet
passes through each switch.  However, your worst enemy is would no
doubt choose a far worse permutation, such as $\pi(i) = (N - 1) - i$.
Now you have no choice: you must route every single packet through the
root node!  Thus, the congestion of the complete binary tree is $N$,
which is absolutely horrible.  Congestion is the downfall of the
complete binary tree.

\iffalse
A communication network that can cope with even the worst permutation
routing problem without any switch becoming overloaded must be pretty
good.  This observation motivates our definition of congestion.  The
\term{congestion} of a network is the largest number of packets that
pass through any switch in the \textit{best} solution to the
\textit{hardest} permutation routing problem.  More precisely, the
congestion is the:
%
\begin{center}
\begin{tabular}{ll}
       & maximum over all permutations $\pi$ \\
of the & minimum over all sets of paths $P_{0, \pi(0)}, \ldots, P_{N-1, \pi(N-1)}$ \\
of the & maximum over all switches $s$ \\
of the & number of paths $P_{i, \pi(i)}$ containing switch $s$.
\end{tabular}
\end{center}
\fi

\instatements{\newpage}

\section*{An Extended DeBruijn Graph}

Can you find a sequence of $a$'s, $b$'s, and $c$'s that contains every
three-letter combination exactly once?  For example, here is a
sequence that contains every \textit{two}-letter combination exactly
once:
%
\[
caabaccbbc
\]
%
Don't try to hard!  We'll help you solve this problem using a
generalization of the deBruijn graph.

\bparts

\ppart The vertices of the extended deBruijn graph are all 2-letter
combinations, $aa$, $ab$, $ac$, $ba$, etc.  There are three directed
edges from vertex $x_1 x_2$:

\begin{itemize}
\item an edge to vertex $x_2 a$ labeled $a$
\item an edge to vertex $x_2 b$ labeled $b$
\item an edge to vertex $x_2 c$ labeled $c$
\end{itemize}

Draw this graph.  Be neat!  You might want to use a whole page.

\solution{
\begin{center}
\includegraphics[height=4in]{ext-debruijn}
\end{center}
}

\ppart An \term{Euler tour} is a walk through a graph that contains
every edge exactly once and that starts and ends at the same vertex.
A connected graph in which every vertex has an equal number of
incoming and outgoing edges, as this one does, \textit{always} has an
Euler tour.  Find an Euler tour in your extended deBruijn graph.

\solution{In the preceding diagram, the edges marked 1, 2, 3,
etc. define an Euler tour.  Many other solutions are possible.}

\ppart Write down $aa$ and then list the labels on edges traversed by
your Euler tour, starting at vertex $aa$.  The resulting string of
letters should contain every three-letter combination exactly once.
Why does this work?

\solution{If we start at vertex $aa$, then the Euler tour proceeds
through edges $13, \ldots, 27, 1, \ldots, 12$ and generates the
following sequence of labels:
%
\[
aaabcaacacbaccabbbccbccbbabaa
\]
%
When the tour is at vertex $x_1 x_2$, the last two symbols in the
sequence are $x_1 x_2$.  Since the tour passes though each outgoing
edge of each vertex exactly once, the sequence contains all of $x_1
x_2 a$, $x_1 x_2 b$, and $x_1 x_2 c$ for each $x_1$, $x_2$.  Thus, the
sequence contains every three-letter combination exactly once.}

\ppart This extended deBruijn graph could serve as a communication
network, if we attached input and output terminals to each vertex.
What would the diameter be?

\solution{There is a path from any vertex $x_1 x_2$ to any vertex $y_1
y_2$ containing exactly three switches: $x_1 x_2$, $x_2 y_1$, and $y_1
y_2$.  Thus, the diameter is at most 3.  There is no path from $aa$ to
$cc$ with fewer than three switches, so the diameter is exactly 3.}

\ppart \textbf{(challenge) } Can you design a network with the same
diameter, but \textit{more} 3-input/3-output vertices?

\solution{Add a vertex $v$.  Remove the self-loops on vertices $aa$,
$bb$, and $cc$.  Put two arcs between $v$ and each of these vertices,
one running in each direction.}

\eparts
