        \problemdata       % Takes 5 *mandatory* arguments
        {bassett-bus}             % latex-friendly label for the prob.
        {relations}  % The topic(s) of the problem content.
        {Velleman \S 4.5 exercise 1}               % Source (if known)
        {F01 PS3-2} % Usage (list ones you are aware of).
        {}        % Last revision info (author, date).


\begin{problem}
The Bassethound Bus Company is trying to decide on \emph{one-way} bus
routes to run among the cities
\begin{quotation}\noindent
San Francisco, Chicago, Dallas, New York, and Washington D.C.
\end{quotation}
Bassethound wants to make sure that there is always some way to follow its
routes and get from any of the cities to any other.  We will represent
Bassethound's routes by a binary relation, $B$, on the set, $C$, of cities
above.

\begin{problemparts}
\problempart Succinctly express the property that Bassethound wants $B$ to have
using relational and set operators on $B$ and $C$.

\solution{From every city $c \in C$ there should be a possible
series of bus routes to get to any other city $c' \in C$. This implies that
$\forall (c, c') \in C \cross C, (c,c') \in B^*$ (transitive closure
of B). In other words, $C \cross C \subseteq B^*$.

Note that, since we know that $B^* \subseteq C \cross C$, it
equivalent to require that $C \cross C = B^*$.}

\end{problemparts}

However, Bassethound wants to run as few bus routes as possible.  That is,
Bassethound wants the size, $\card{B}$, of $B$ to be as small as possible.

\begin{problemparts}
\problempart What is the smallest possible value of $\card{B}$?
Explain.

\solution{5. We can connect the cities in a ring with one way edges
between them. So for example, $B$ could be the set $\set{(SF,C) ,
(C,D) , (D,NY), (NY,W) , (W, SF)}$.

5 is the minimum number of edges possible because for each city to be
accessible there must be at least one edge entering the city. Hence
$B$ can not have fewer than 5 edges.
}

\problempart
Is the smallest satisfactory $B$ unique?

\solution{No, since we could connect the cities in different orders.}

\problempart Unfortunately, Bassethound has a legacy problem.  They already have
a set of routes, $A$, that connect all the cities.  While they can cancel
routes easily, new routes are expensive, and they are reluctant to add
them.  Starting from $A$, can Bassethound arrive at a smallest size $B$
solely by cancelling routes?  Give a counterexample showing that it can't,
or explain how it can.

\solution{If $A$ has round trip direct from NY to each other city
(not unusual for these companies to have hubs), no route can be
cancelled and still maintain connectivity. But $A$ has 8 routes, not
the minimum number of 5. In general if a ring does not already exist
in the original $A$ digraph, there is no way to arrive at one.}

\end{problemparts}
\end{problem}