\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 
\usepackage{eepic}

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query
\renewcommand{\coursecopyrightnames}{Dr.~Radhika~Nagpal}

\begin{document} 
\inclassproblems{3M}            % !! start the paper


{\em Definition:} The \emph{composition} of relations $R \subseteq A
\times B$ and $S \subseteq B \times C$ is the relation

$S \circ R =\{(a,c) \mid \exists b \mbox{ such that } (a,b) \in R \wedge (b,c) \in
S \}.$

% Made this up (RAD)
% based on Bassethound problem from last year (fall 01, pset3)
\begin{problem}

Recently MIT students have been taking a hard look at the haphazard
building layout, and have been asking some hard questions. As always
they know they can use their superior mathematical skills to get some
real answers to those hard questions.

They decide to express the MIT building layout as a relation. Let $C$ be
the set of all building numbers and let $R$ be the relation on the set
$C$ such that $(a,b) \in R$ if building $a$ and building $b$ are
connected together. Note that if $(a,b) \in R$, then $(b,a)$ is also in
$R$.  We will define a building to be connected to itself, so $(a,a) \in
R$.

\begin{problemparts}

\problempart For this part only, let $R$ be the following partial map
of the connection between the MIT buildings 10,13,12,4,8 and
26.

\input{cp3M-figure1.latex}

% \begin{verbatim}
%                    26
%         13   12    |
%         |    |     |
%         10---4-----8
% \end{verbatim}

Compute $R^2 = R \circ R$. 
Compute $R^3 = R \circ R^2$.


\solution{

$R^2$ consists of all pairs of buildings that are connected via exactly
one building. Since there are self-loops in the connectivity graph (each
building is connected to itself), $R^2$ includes everything which is in
$R$ as well. For example, $(13,10)$ which is in $R$ must also be in
$R^2$ because you can go from building $13$ to building $10$ ``via one
building'' by just going around building $13$ once and then moving on to
building $10$. That said, we conclude that
\[R^2 = R \union \Big\{(13,4),
(10,12),(10,8),(12,10),(12,8),(4,13),(4,26),(8,10),(8,12),(26,4)\Big\}
\]
Similarly, $R^3$ contains everything which is
in $R^2$ (because of the self-loops), plus all the extra pairs that we
get by allowing connections via \emph{two} intermediate buildings. So we
have:$$R^3= R^2 \union \Big\{(13,12),(13,8),(10,26),(12,26),(8,13),(26,12),(26,10)\Big\}
$$
%\input{cp3M-1.pic}
}

\problempart What does the relation $R^2$ represent in terms of
connectivity between buildings? Can you generalize this? (You do not
have to prove it but you should have a good argument why.)

\solution{$R^2$ is the set of all pairs of buildings that are connected
via exactly 1 intermediate building. Similarly $R^3$ is the set of all
pairs of buildings that are connected via exactly 2 intermediate
buildings. This notion can be generalized to $R^n$, where $(a,b)$ is in
$R^n$ iff $a$ and $b$ are connected via exactly $n-1$ intermediate
buildings. We can recursively define $R^n$ as $R \circ R^{n-1}$.
Induction would thus be a natural way to go about proving this. It is
worth looking at the proof, which can be found both in the notes and in
Rosen.

It is important to notice that \emph{in general} it is not necessarily
true that $R^n$ must include $R^{n-1}, R^{n-2}, \ldots, R$ as well. In
our example, this was the case because the graph included self-loops and
bidirectional edges (symmetric relation), so one can meet the requirement
of going from building $a$ to building $b$ through $n-1$ intermedite
buildings by going around building $a$ as many times as necessary and
then proceeding to building $b$ (there are many similar time-wasting
ways to meet the requirement).

}

\problempart One of the important questions for 6-3 students was, is
it possible to get from building 36 to building 10 without crossing
more than 5 other buildings? Write a predicate in terms of $R$,
using relational and set operators, that expresses this condition.

\solution{The key to solving this is to first write an expression for
the set of all buildings that are connected via 5 or fewer
buildings. In general, this would be $(R \union R^2 \union R^ ... R^6)$.
As explained above, in our case this is the same as $R^6$. Then the
predicate on $R$ is $(36,10) \in R^6$.
}

\problempart The MIT students would like to be able to get from any
building to any other building, without having to go outside. Write
the condition on $R$ that must be satisfied in order for this to be
true.

\solution{Let $\card{C}$ be $n$. In other words there are $n$
different buildings. The furthest apart two buildings can be, and
still be connected, is to be connected via $n-2$ other buildings
(prove this to yourself). Therefore the set $(R \union R^1 \union R^
... R^{n-1})$ represents all the pairs of buildings that can reach one
another without going outside. Because of the self-loops, this is just
$R^{n-1}$ since this set includes everything else as well.

However we want every pair of buildings to be connected. The set of all
pairs of buildings is $C\times C$. Therefore the condition we want to
satisfy is $ C \times C\subseteq R^{n-1}$ (``the set of all possible pairs of
buildings is a subset of the set of buildings that you can reach through $n-2$
intermediate buildings'').


%BECAUSE OF THE SELF-LOOP, THIS MAY BE A POOR EXAMPLE OF TRANSITIVE
%CLOSURE..

%Another way of thinking about this condition is that we want $R$ to be
%connected, and the set ($(R \union R^1 \union R^ ... R^n)$ is called
%the transitive closure or connectivity relation on $R$.)}
}


\problempart (*) However, MIT administration wants to keep the number of
connections between building as small as possible. In other words, MIT
wants the size, $\card{R}$, of $R$ to be as small as possible. What is
the smallest $R$ that satisfies the requirement in part (d)?  Is the
smallest $R$ unique?

\solution{The smallest digraph such that all the buildings are
connected would be to connect them in a straight line. The number of
edges in that graph is $n-1$. How do we know that this is the smallest
number of edges? Next week we will learn a theorem that says that the
smallest connected graph with vertices $n$ has at least $n-1$
edges. Each edge contributes two pairs therefore $\card{R} =
2(n-1)$. The smallest digraph is not unique, for starters we can
connect the buildings in a different order in the line. But there are
many other connected graphs with $n$ vertices and $n-1$ edges.
}

\end{problemparts}

\end{problem} 

\iffalse
\begin{problem}
OLD 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^*$.}

\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 canceling 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
canceled 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} 
\fi

\begin{problem}

Recall that the \emph{composition} of relations $R \subseteq A
\times B$ and $S \subseteq B \times C$ is the relation
\[
S \circ R =\{(a,c) \mid \exists b \mbox{ such that } (a,b) \in R \wedge
(b,c) \in S \}.
\]
If we represent relations as matrices, then we can compute the
composition of two relations by a ``boolean'' matrix multiplication of
their matrices. Boolean matrix multiplication is the same as matrix
multiplication except that ``$+$'' is replaced by $\vee$ (Boolean OR)
and ``$\times$'' is replaced by $\wedge$ (Boolean AND).

Prove that the matrix representation of $S o R$ is equal to the
boolean product of $M_R$ and $M_S$, where $M_R$ is the matrix
representing $R$ and $M_S$ is the matrix representing $S$.

\solution{Let $M_P$ be the boolean product of $M_R$ and $M_S$ (notice
that $M_P$, $M_R$ and $M_S$ are all $n\times n$ square matrices). What
we want to prove is that
\[
(i,j) \in S\circ R  \Longleftrightarrow  M_P (i, j)=1
\]

Recall that by the definition of composition, $(i,j) \in S\circ R $
iff there exists a $k$ such that $(i,k) \in R$ and $(k,j) \in
S$. Also, by the definition of boolean matrix multiplication,

\[
M_P (i,j) = \underbrace{\left[M_R(i,k_1) \wedge
M_S(k_1,j)\right]}_{k_1 \text{ is the ``link''}} \vee 
\underbrace{\left[M_R(i,k_2) \wedge
M_S(k_2,j)\right]}_{k_2 \text{ is the ``link''}}\vee 
\ldots \vee\underbrace{\left[M_R(i,k_n) \wedge
M_S(k_n,j)\right]}_{k_n \text { is the ``link''}}
\]

\begin{description}
\item[Case 1:($\Longrightarrow$)] If $(i, j) \in S\circ R$, then for
at least one $k$, say $k'$, $(i,k') \in R$ and $(k',j) \in
S$. Consequently, $M_R(i,k')=1$ and $M_S(k',j)=1$. This turns
$\left[M_R(i,k') \wedge M_S(k',j)\right]$ true, and hence $M_P(i,
j)=1$.

\item[Case 2: ($\Longleftarrow$)] If $M_P(i, j)=1$ then there is at least one
$k$, say $k'$,  for which $\left[M_R(i,k') \wedge
M_S(k',j)\right] =1$. This means that both $M_R(i,k')=1$ and $M_S(k',j)=1$.
Since $M_R$ and $M_S$ are the matrix representations of $R$ and $S$, we
can conclude that $(i,k')\in R$ and $(k',j)\in S$, and so, by the definition
of composition, $(i,j)\in S\circ R$ 
\end{description}
 
}

\end{problem}


\end{document}


\end{problem}


\end{document}
