\documentclass[11pt,twoside]{article}
\usepackage{graphicx}
\usepackage{macros-course-lectures}

\begin{document}

\mainlylecture

\lecture{notes7}{Graphs and Trees}{March 1, 2000}



\section{Graphs}

\begin{breakperiods}
Just like DAGs are a nice way to think about partial orders, graphs in
general are a nice way to think about general relations.  They give a picture
of the relation, which can be much more revealing than a list of
tuples.  They motivate the study of other properties.


\subsection{Definitions}

We'll start with a bunch of definitions.  Many are inherited from the
definition of relations.  Others are slightly modified for
convenience.  Yet others are new.

\subsection{Simple Graphs}

A \emph{graph} is a pair of sets $(V, E)$.  The elements of $V$ are
called \emph{vertices}.  The elements of $E$ are called \emph{edges}.
Each edge is a pair of distinct vertices.  We are going to concentrate
on \emph{undirected} graphs.  These correspond to symmetric relations.
If edge $(u,v)$ is present, edge $(v,u)$ is also present.  Therefore,
we denote such an undirected edge by the unordered \emph{set}
$\{u,v\}$. However, it is very common to use $(u,v)$ to denote
undirected edges, so be careful when you read mathematical texts. The
edge $\{u, v\}$ is said to be \emph{incident} to vertices $u$ and~$v$.
The vertices $u$ and~$v$ are said to be \emph{adjacent} or
\emph{neighbors}.  Phrases like, ``an edge joins $u$ and~$v$'' and
``the edge between $u$ and~$v$'' are common. Graphs are also
sometimes called \emph{networks}\.  Vertices are also sometimes called
\emph{nodes}\.  Edges are sometimes called \emph{arcs}\.
\end{breakperiods}
\begin{figure}
  \centerline{\includegraphics[height=2in]{figures/graph}}
  \caption{This is a picture of a graph $G = (V, E)$.  There are four
    vertices and four edges.  The set of vertices $V$ is $\{1, 2, 3,
    4\}$.  The set of edges $E$ is $\{\{1,2\}, \{1,3\}, \{2,3\},
    \{3,4\}\}$.  Vertex~1 is adjacent to vertex~2, but is not adjacent
    to vertex~4.}
  \label{fig:graph}
\end{figure}


\subsection{Not-So-Simple Graphs}

There are actually many variants on the definition of a graph\.  The
definition in the preceding section really only describes \emph{simple
  undirected graphs}\.  There are many ways to complicate matters.

\forstudents[Assorted extensions appear in the notes]{ 

\subsubsection*{Multigraphs}

In a simple graph, there are either zero or one edges joining a pair
of vertices\.  In a \emph{multigraph}, multiple edges are permitted
between the same pair of vertices.

\subsubsection*{Self-Loops}

In a simple graph, each edge is a pair of \emph{distinct} vertices\.
A \emph{self-loop} is an edge that connects a vertex to itself\.
\begin{figure}
  \centerline{\includegraphics[height=1.5in]{figures/multigraph}}
  \caption{This is a picture of a multigraph with a self-loop.  In
    particular, there are three edges connecting vertices 1 and 2 and there
    is a self-loop on vertex 3.}
  \label{fig:multigraph}
\end{figure}

\subsubsection*{Directed Graphs}

In a \emph{directed graph} or \emph{digraph}, edges are regarded not as
lines, but as arrows.  (The technical difference is that in a simple
graph each edge is an unordered pair of vertices, whereas in a
directed graph each edge is an ordered pair.)
\begin{figure}
  \centerline{\includegraphics[height=1.5in]{figures/digraph}}
  \caption{This is a picture of a directed graph or digraph.}
  \label{fig:digraph}
\end{figure}

\subsubsection*{Weighted Graphs}

Sometimes it is useful to associate a number with each edge in a
graph. These numbers are usually called \emph{weights}.  The weight
of an edge $\{u,v\}$ is often denoted $w(\{u,v\})$ or $w(u,v)$.
}

\subsection{Graphs in the Real World}

There are many real-world phenomena that
can be described nicely by graphs.  Here are some examples:
\begin{description}
\item[The Internet.]  Here the vertices are routers and the edges are
  assorted links---fibers, wires, etc.
\item[Airline Connections.] Here the vertices are airports and edges
  are flight paths\.  We could indicate the direction that planes fly
  along each flight path by using a directed graph\.  We could use
  weights to convey even more information\.  For example, $w(i, j)$
  might be the distance between airports $i$ and $j$, or the flying
  time between them, or even the air fare.
\item[Precedence Constraints.] Suppose you have a set of jobs to
  complete, but some must be completed before others are begun\.  (For
  example, Atilla the Hun advised that you should always to pillage
  \emph{before} you burn.)  Here the vertices are jobs to be done\.
  Directed edges indicate constraints; there is a directed edge from
  job $u$ to job $v$ if job $u$ must be done before job $v$ is begun.
\item[Program Flowcharts.] Each vertex represents a step of
  computation\.  Directed edges between vertices indicate control
  flow.
\item[Bayes Nets.]  These are graphs that indicate dependencies between
  random variables in statistical machine learning problems. 
\end{description}
\begin{figure}
  \centerline{\includegraphics[height=3.0in]{figures/zoo}}
  \caption{The types of graph shown here are so common that they
    have names. (a) The \emph{empty graph} on five vertices, $E_5$.  An empty
    graph has no edges at all. (b) The \emph{cycle} on five vertices, $C_5$.
    (c) The \emph{complete graph} on five vertices, $K_5$.  A complete
    graph has 
    an edge between every pair of vertices.  (d) A five-vertex
    \emph{line graph.} 
    (e) A $5 \times 5$ 2-dimensional \emph{mesh.}}
  \label{fig:zoo}
\end{figure}



\subsection{Adjacency Matrices}

We defined a graph in terms of a set of vertices and a set of edges\.
In a computer it is often represented by an \emph{adjacency
  matrix}---another name for the matrix representation of the
underlying relation.

Some variants of simple graphs can also be described well by matrices\.
For example, a weighted graph is naturally associated with a matrix
where $w(i, j)$ is the entry at row $i$ and column $j$.

\subsection{Subgraphs}

A \emph{subgraph} of a graph $G = (V, E)$ is a graph $G' = (V' , E')$
such that $V' \subseteq V$ and $E' \subseteq E$\.  For example, a
triangle is a subgraph of $K_4$ (the complete graph on four vertices),
but not of $C_4$ (a cycle with four vertices).


\subsection{Vertex Degree}

The \emph{degree} of a vertex is the number of incident edges\.  The
degree of vertex $v$ is often denoted $d(v)$\.  For example, referring
to Figure~\ref{fig:zoo}, every vertex in an empty graph has degree 0,
but every vertex in a cycle has degree 2\.  A look at the other
examples suggests the following theorem:
\begin{theorem}
  In a graph with $m$~edges, the sum of degrees of the vertices is~$2m$.
\end{theorem}
\begin{proof}
  By induction on the number of edges\.  Zero edges means the sum is
  zero, so the base case is clear\.  Our inductive hypothesis is that
  the sum of the degrees in any graph with $m$~edges is~$2m$\.
  Consider any graph with $m+1$ edges\. Take away one of the edges\.
  The remaining graph has $m$~edges, so the sum of the degrees is~$2m$
  by the inductive hypothesis\. Putting back the edge we removed
  increments two degrees by one, so the degree sum becomes $2m+2 =
  2(m+1)$.
\end{proof}
\begin{corollary}
  In every graph, the number of odd-degree vertices is even.
\end{corollary}
\begin{proof}
  If we had an odd number of odd degrees, the degree sum would be
  odd\. But it is even by the above theorem\. This is a contradiction\.
\end{proof}




\section{Graph Coloring}

Now it's time to discuss final exams\.  The MIT Schedules Office needs
to assign 
a time slot for each final.  This is not easy, because some students
are taking several classes with finals, and a student can take only
one test during a particular time slot\.  The Schedules Office wants to
avoid all conflicts, but wants to make the exam period as short as
possible.

This scheduling problem can be represented by a graph\.  Let each
vertex represent a course.  Put an edge between two vertices if there
is some student that is taking both courses\.  Identify each possible
time slot with a color\.  For example, Monday 9--12 is red, Monday
1--4 is blue, Tuesday 9--12 is green, etc.  The problem of assigning
time slots to exams is then equivalent to the problem of assigning
colors to vertices.

If a student is taking two courses, then there is an edge between two
vertices\.  If these vertices are the same color, then there is a
conflict because the student has to take exams for the two courses at
the same time\.  Therefore, the problem is to color each vertex of the
graph so that no adjacent vertices have the same color and so that the
number of colors used is as small as possible\.
\begin{figure}
  \centerline{\includegraphics[height=2in]{figures/exams}}
  \caption{This graph represents the exam scheduling problem.  Each
    vertex stands for a course.  An edge between two vertices indicates
    that a student is taking both courses and therefore the exams can not
    be scheduled at the same time.  Each exam time slot is associated with
    a color.  A schedule that creates no conflicts corresponds to a
    coloring of the vertices such that no adjacent vertices receive the
    same color.}
  \label{fig:exams}
\end{figure}
In general, the minimum number of colors needed to color the vertices
of a graph $G$ so that no two adjacent vertices are the same is called
the \emph{chromatic number} and is written $\chi(G)$.\footnote{This is
the Greek letter ``chi'' pronounced ``key'' by the ancient Greeks and
``kie'' by mathematicians and frats.}  For example, if $G$ is the
3-cycle or triangle graph, then $\chi(G) = 3$.

In general, finding the chromatic number of a graph is very hard\.
However, we can at least put some upper bounds on the chromatic
number\.  For example, the chromatic number of an $n$-vertex graph is
certainly at most $n$, since every vertex could be assigned a
different color\. We can do better, however:
\begin{theorem}
  Any graph in which the maximum vertex degree is $\Delta$ can be
  colored with at most $\Delta+1$ colors.
\end{theorem}
This theorem implies, for example, that a graph with thousands of
vertices, each of degree 3, requires at most 4 colors\.  The proof is
surprisingly easy:
\begin{proof}
  The proof is by induction\.  Let $P(n)$ be the proposition that every
  graph with $n$ vertices, all with degree at most $\Delta$, can be
  colored using at most $\Delta + 1$ colors.

  For the base case, $P(1)$, we consider a single vertex with degree
  zero\.  In this case, $\Delta = 0$ and the algorithm requires $ 1 \le
  \Delta+1$ colors.

  In the inductive step, assume $P(n)$ to prove $P(n+1)$\.  Let $G'$ be
  the graph obtained from $G$ by removing a vertex $v$ and all its incident
  edges\.  No vertex in $G'$ has degree greater than $\Delta$, since
  removing a vertex and edges can not increase the degree of
  any other vertex\.  By induction, we can color $G'$ with at most
  $\Delta + 1$ colors.  

  Now we need to ``put back'' the vertex $v$ we removed and color it\.
  But $v$ has at most $\Delta$ neighbors in $G$\.  Among them, these
  other vertices can ``use up'' at most $\Delta$ colors\.  Thus, one of
  our $\Delta+1$ candidate colors is still available to color the
  replaced vertex without violating the coloring rules.
\end{proof}
\begin{remark}
  The above proof actually gives a recursive algorithm producing a
  coloring: Take away any vertex from~$G$ and recursively color the
  remaining graph, then give~$v$ a valid color. The base case is to
  color a one-vertex graph.
\end{remark}



\section{Connectivity}

Is a graph all in one piece or composed of several pieces\?  To walk
from one vertex to another, how many edges must one cross\?  Are there
many different routes or just one\?  These are questions about
connectivity.

\subsection{Basic Notions of Connectivity}

In a graph, a \emph{path} from a vertex $u$ to a vertex~$v$ is a
sequence of edges $\{u, x_1\}, \{x_1, x_2\}, \ldots, \{x_k, v\}$\.  A
path may contain the same edge or vertex multiple times.  A path can
also be described by the sequence of vertices encountered---i.e., a
path is a vertex sequence $u=x_0,x_1,\ldots,x_k,x_{k+1}=v$ such that
each $\set{x_i,x_{i+1}}$ is an edge.

In a \emph{simple path}, no vertex or edge is crossed more than once\.
However, as a special case, the initial and final vertices may be the
same\.  In other words, $u, x_1, x_2, \ldots, x_k$ are all distinct
vertices, and $x_1, x_2, \ldots, x_k, v$ are all distinct vertices,
but $u = v$ is permitted.

In an undirected graph, there is a path from $u$ to~$v$ iff there is a
path from $v$ to~$u$; 
one path is obtained from the other by reversing the sequence of
edges\.  The same statement holds for simple paths.

A \emph{circuit} is a path from a vertex back to itself, i.e. a
sequence of edges $\{u, x_1\}, \{x_1, x_2\}, \ldots, \{x_k, u\}$.  A
\emph{cycle} is a simple path from a vertex back to itself.
\begin{definition}
  We say two vertices are \emph{connected} if there is a path between
  them.
\end{definition}
\begin{lemma}
  There is a path between two vertices iff there is a simple path
  between them.
\end{lemma}
\begin{proof}
  We first prove the easy direction: if there is a simple path 
  between two vertices 
  there is obviously a path between them\. Now we prove the other
  direction: 
  that if there is path between the vertices there is a simple path
  between them.

  Suppose that there is a path between the two vertices\.  Consider
  the shortest path between the two vertices\. (This uses the
  well-ordering principle: We consider the set of paths between the
  two vertices, it is non-empty, so there exists a shortest path.)
  Suppose it is not a simple path---so some vertex is repeated\.  So
  the path has the form $a_0,\ldots,a_i,\ldots,a_j,\ldots,a_k$ where
  $a_i=a_j$\.  But then $a_0,\ldots,a_{i},a_{j+1},\ldots,a_k$ is a
  shorter path, a contradiction.
\end{proof}
So we could equally say that vertices are connected iff there is a
simple path between them.
\begin{definition}
  A graph is \emph{connected} if there is a path between every pair of
  distinct vertices.
\end{definition}
For example, referring back to Figure~\ref{fig:zoo}, the empty graph
is disconnected, but all others shown are connected.

Connectedness is an equivalence relation\. It is clearly reflexive (if
we allow for length 0 paths)\. It is symmetric because we can reverse
paths in an undirected graph\.  It is transitive because we can
concatenate (attach at the endpoints) paths.

Like any equivalence relation, connectedness induces a partition of
the vertices into equivalence classes\.  Each equivalence class is
called a \emph{connected component}\.  A component is a set of vertices
that can all reach each other, but can't reach any other vertices.

We can also say that a connected component of a graph is a subgraph
that is connected and maximal\.  That is, if any more vertices of the
graph are
added to the subgraph, then it is no longer connected (because the
added vertices are in another component)\.  For example,
every connected graph has exactly one connected component\.  The empty
graph on $n$~vertices has $n$~connected components\.
\begin{figure}
  \centerline{\includegraphics[height=1.5in]{figures/3comp}}
  \caption{This is a picture of a graph with 3 connected components.}
  \label{fig:3comp}
\end{figure}



\subsection{Cuts}

Another way to look at connectivity is to see what prevents it.
\begin{definition}
  An \emph{empty cut} of a graph $G$ is a partition of the vertices $V$
  into two nonempty sets $W$ and $V-W$ such that no edge connects $W$
  and $V-W$ (that is, no edge has one endpoint in each set).
\end{definition}
\begin{lemma}
  A graph is connected iff it has no empty cuts.
\end{lemma}
\begin{proof}
  Suppose $G$ has an empty cut $(W,V-W)$\.  Let $w \in W$ and $v \in
  V-W $\.  We show by contradiction that there is no path from $w$
  to~$v$, which means $G$ is not connected\.  To do so, suppose there is a
  path $w=p_0,\ldots,p_k=v$ from $w$ to $v$\.  Consider the
  smallest~$j$ such that $p_j \in V-W$\. (This is using the
  well-ordering principle: the set of~$j$ such that $p_j \in V-W$ is
  nonempty since $k$~is in the set, so it has a smallest
  element~$j$.) Note that $j \neq 0$ since $w=p_0 \in W$, so $p_{j-1}$
  is a vertex on the 
  path that is not in~$W$\.  So the edge $\{p_{j-1},p_j\}$ has one
  endpoint in~$W$ and the other in $V-W$, contradicting the claim that
  $(W,V-W)$ is an empty cut.
  
  For the other direction suppose that $G$~is disconnected; we
  construct an empty cut\.  By assumption there is a pair of vertices
  $v$ and~$w$ such that there is no path from $v$ to~$w$\.  Let $W$ be
  the set of vertices connected to $w$ (by a path)\.  Then $(W,V-W)$
  is an empty cut\.  For suppose the cut is not empty\.  Then there is
  an edge $\{x,y\}$ with $x\in W$ and $y \in V-W$\.  But there is a
  path from $w$ to~$x$\.  Adding the edge $\{x,y\}$ gives a path from
  $w$ to~$y$, so $y \in W$\.  This is a contradiction.
\end{proof}
Note that we've used the well ordering principle.  As is always the
case, we can rephrase this proof as a induction.  In this case, we
take our assumption (that $p_0 \in W$) and prove a conclusion by
induction (that $p_k \in W$) that contradicts another fact (that $p_k
\in V-W$)\.  This shows that our assumption that a path exists must be
false.  To prove the contradictory claim (that $p_k \in W$) we argue
by induction that $(\forall i)p_i \in W$\.  As a base case this is
true for $p_0$ by assumption\.  For the inductive step, suppose $p_i
\in W$\.  There is an edge $\set{p_i,p_{i+1}}$ on the path, but no
edge with one endpoint in $W$ and one in $V-W$ (since the cut is
empty)\.  Thus, since $p_i \in W$, we also have $p_{i+1} \in W$\.  In
particular, $p_k \in W$, proving our (contradictory) claim.


\subsubsection*{A False Theorem about Connectivity}

If a graph is connected, then every vertex must be connected to some
other vertex\.  Is the converse of this statement true\?  If every
vertex is connected to some other vertex, then is the graph connected\?
The answer is no\.  In fact, the graph with three connected components
showing in Figure~\ref{fig:3comp} is a counterexample\.  So what is wrong
with the following proof?
\begin{falsethm}
  If every vertex in a graph is adjacent to another vertex, then the
  graph is connected.
\end{falsethm}
\begin{figure}
  \centerline{\includegraphics[height=1.5in]{figures/false}}
  \caption{This picture accompanies the false proof.  Two situations
    are depicted.  In one, vertices $x_1$ and $x_2$ both lie among the
    first $n$ vertices, and so there is a connecting path by induction.
    In the second, $v = x_1$ and $x_2$ is among the first $n$ vertices.
    In this case there is a connecting path because there is an edge from
    $v$ to $u$ and a path from $u$ to $x_2$ by induction.}
  \label{fig:false}
\end{figure}
\begin{proof}[Incorrect proof]
  The proof is by induction\.  Let $P(n)$ be the predicate that if
  every vertex in an $n$-vertex graph is adjacent to another vertex,
  then the graph is connected\.  In the base case, $P(2)$ is trivially
  true because there are only two vertices. If they are adjacent to
  each other, the graph is connected.
  
  In the inductive step, we assume $P(n)$ to prove $P(n+1)$\.  Start with
  an $n$-vertex graph; this is connected by induction.  Now add a vertex
  $v$\.  By assumption $v$ is connected to one of the first $n$ vertices;
  call that one $u$.
  
  Now we must show that for every pair of distinct vertices $x_1$ and
  $x_2$, there is a path between them\.  If both $x_1$ and $x_2$ are
  among the first $n$ vertices, then there is a path by induction\.
  Otherwise, one of the vertices is $v$ (say $x_1$) and the other is
  among the first $n$ vertices\.  These are connected by the path from
  $x_1$ to $u$ to $x_2$ as shown in the figure.
\end{proof}
The error is in the early statement ``Start with an $n$-vertex graph;
this is connected by induction\.'' The induction hypothesis does not
say that every $n$-vertex graph is connected, but only, ``\emph{if
every vertex in an $n$-vertex graph is adjacent to another vertex},
then the graph is connected''\.

The core problem here is called ``buildup error'' and is a common
source of mistakes in inductive proofs.

The name buildup error arises from the intuition that usually drives
the error: that in order to create an instance of size $n+1$, you take
an instance of size $n$ and extend it by one\.  If you are careless,
you can forget some of the possible ways a size $n+1$ problem can
arise: you fail to ``build'' all the size $n+1$ instances, so your
proof doesn't cover all the instances.

More formally, buildup error occurs when the induction hypothesis
$P(n)$ is itself an implication of the form $A(n) \Rightarrow B(n)$\.
In this instance, $A(n)$ is the statement, ``every vertex in an
$n$-vertex graph is adjacent to another vertex'' and $B(n)$ is the
statement, ``the graph is connected''.

In the inductive step of a correct proof, we assume $A(n) \Rightarrow
B(n)$ in order to prove $A(n+1) \Rightarrow B(n+1)$\.  In an erroneous
proof, we assume $B(n)$ in order to prove $A(n+1) \Rightarrow B(n+1)$\.
This is precisely what happened; we assumed, ``the graph is
connected'' rather than, ``if every vertex in an $n$-vertex graph is
adjacent to another vertex, then the graph is connected''.

\subsubsection*{A True Theorem about Connectivity}

If a graph has too few edges, then there can not be a path between
every pair of vertices\.  More generally, a graph with a very small
number of edges ought to have many connected components\.  (Remember,
``many connected components'' does not mean ``very connected'';
rather, it means ``broken into many pieces''!)  The following theorem
generalizes these observations.
\begin{theorem}
  A graph with $k$ edges and $n$ vertices has at least $n - k$ connected
  components.
\end{theorem}
For example, a graph with 0 edges and $n$ vertices has at least $n - 0
= n$ connected components\.  A graph with $100$~vertices and $35$~edges
must have at least $100 - 35 = 65$ distinct connected components.
\begin{proof} 
We fix a particular $n$ and prove the theorem for that $n$ by
  induction on $k$\.  (This may seem odd, 
  because for $k > n$, the theorem says that the number of connected
  components is greater than some negative number!  This is useless,
  but certainly true, so there is no harm.)
  
  Let $P(k)$ be the predicate that an $n$-vertex graph with $k$ edges
  has at least $n - k$ connected components\.  In the base case,
  $P(0)$ holds because an $n$-vertex graph with 0~edges does have at
  least $n - 0 = n$ components.
  
  In the inductive step, we assume that an $n$-vertex graph with $k$
  edges has at least $n - k$ connected components and prove that an
  $n$-vertex graph with $k + 1$ edges has at least $n - k - 1$
  connected components\.  Let $G$ be a graph with $n$ vertices and $k
  + 1$ edges\.  Remove one edge $e$\.  The resulting graph has $n$
  vertices and $k$ edges\.  By induction there are at least $n - k$
  connected components.
  
  There are two possibilities when we replace the edge $e$\.  First,
  if $e$ is incident to two vertices in the same connected component,
  then the number of connected components is unchanged at $n - k$\.
  Otherwise, if $e$ is incident to vertices in two different connected
  components, then the two become a single connected component\.  This
  reduces the number of connected components by one to $n - k - 1$\.
  In both cases, the number of connected components is at least $n - k
  - 1$ as claimed.
\end{proof}
If a graph has fewer than $n-1$ edges, then the theorem implies it has
more than one connected component\.  Therefore, a graph must have at
least $n-1$ edges to be connected\.  In fact, there are graphs with $n
- 1$ edges and a single connected component; the line graph of
Figure~\ref{fig:zoo} is an example\.

Is this a complete proof?  Not quite\.  We claimed that adding on edge
reduces the number of connected components by one\.  This is obvious by
picture, but how do we prove it formally?  
\begin{lemma}
  If an edge is added that connects two distinct components of a
  graph, the number of components is reduced by one.
\end{lemma}
\begin{proof}
  Suppose the added edge is $\{v,w\}$, and let $[v]$ and~$[w]$ be the
  connected components containing $v$ and $w$ respectively\.  We claim
  that upon adding edge $\{v,w\}$, we merge $[v]$ and~$[w]$ into a
  single component and affect no other components.
  
  To see that no other component is changed, suppose for contradiction
  that there is some vertex $q$ \emph{not} in the component of $v$
  or~$w$ for which adding $\{v,w\}$ changes its component---that is,
  the set of vertices it can reach\.  There must be a new path from
  $q$ to some other vertex $r$\.  The only way this path can be
  ``new'' is if it uses edge $\{v,w\}$\.  So both $v$ and~$w$ are on
  the path from $q$ to~$r$\.  Suppose without loss of generality that
  $v$ appears first on the path\.  Then there is a path from $q$
  to~$v$ that does not use edge $\{v,w\}$\.  This path existed before
  we added $\{v,w\}$, meaning that $q$ is in the same component
  as~$v$.  This contradicts our initial assumption\.
\end{proof}
\begin{corollary}
  Deleting a graph edge increases the number of components by at most
  one.
\end{corollary}
\begin{proof}
  Suppose deleting edge~$e$ increased the number by more than one\.
  We have just seen that putting~$e$ back can decrease the number of
  components by at most one\.  So deleting~$e$ and putting it back
  would give a net gain in the number of components!  This is a
  contradiction.
\end{proof}




\section{Trees}

Tree are an important special type of graph for CS applications\.
We have just seen that $n-1$ edges are required for connectivity.
They are sometime sufficient (a line)\.
Let's explore the smallest connected graphs\.
What is a good notion of smallest?  No wasted edges.
\begin{definition}
  A \emph{tree} is a connected graph with no cycles.
\end{definition}
\begin{figure}
  \centerline{\includegraphics[height=2in]{figures/tree}}
  \caption{This tree has 11
    \emph{leaves}, which are defined as vertices of degree at most one.
    The remaining 7 vertices are called \emph{internal nodes}.}
  \label{fig:tree}
\end{figure}
The vertices in a tree can be classified into two categories.
Vertices of degree at most one are called \emph{leaves}, and vertices
of degree greater than one are called \emph{internal nodes}.

Trees are often drawn as in Figure~\ref{fig:tree} with the leaves on
the bottom and a single node (called the \emph{root} at the top)\.
Keep this convention in mind; otherwise, phrases like 
``all the vertices \emph{below}'' will be confusing.
\forstudent{(The English mathematician Littlewood once remarked that
  he found such directional terms particularly bothersome, since he
  habitually read mathematics reclined on his back!)}

Trees arise in many problems\.  Family trees are an example---each
node is a person, and there is an edge between any parent and child.
Similarly, the file structure in a
computer system can often be represented by a tree\.  In this case,
each internal node corresponds to a directory, and each leaf
corresponds to a file\.  If one directory contains another, there there
is an edge between the associated internal nodes\.  If a directory
contains a file, then there is an edge between the internal node
and a leaf\.  In both family trees and directories, there can be
exceptions that make the graph not a tree---relatives can marry and
have children, while directories sometimes use soft links to create
multiple directory entries for a given file.

Trees can actually be defined several different ways.
\begin{theorem}
  The following properties of a graph~$G$ are equivalent:
  \begin{enumerate}
  \item $G$ is a connected graph with no cycles 
  \item $G$ is a connected graph that is disconnected by the removal of any
    edge, \ie, a ``minimal'' connected graph.
  \item $G$ is a graph with a unique simple path between every pair of
    vertices
  \end{enumerate}
\end{theorem}
Since the definitions are equivalent, any one of them could have been
taken as the definition of a tree.

Theorems asserting that several mathematical statements are equivalent
are quite common\.  One way to prove such a theorem would be to
consider every pair of statements in turn and prove them equivalent\.
That is, we would prove $1 \Leftrightarrow 2$, $2 \Leftrightarrow 3$,
and $3 \Leftrightarrow 1$\.  This requires proving six implications,
three in each direction.  

This is overkill\.  A simpler approach is to show $1 \Rightarrow 2$, $2
\Rightarrow 3$, and $3 \Rightarrow 1$\.  These three implications are
sufficient to prove every pair of statements equivalent\.  For example,
$2 \Leftrightarrow 3$ follows because we prove $2 \Rightarrow 3$
directly, and prove $3 \Rightarrow 2$ with the two steps $3
\Rightarrow 1 \Rightarrow 2$.

\begin{lemma}
  $(3 \implies 1)$ A graph with a unique simple path between any pair of
  nodes is connected and has no cycles.
\end{lemma}
\begin{proof}
  It clearly meets the definition of connectivity\.  To see there are
  no cycles we argue by contradiction\.  Suppose we have a (simple)
  cycle $v_1,\ldots,v_k,v_1$\.  Then there are 2 simple paths from
  $v_1$ to $v_k$, namely $v_1,\ldots,v_k$ and the edge $\{v_1,v_k\}$.
\end{proof}


\begin{lemma}
  $(1\implies 2)$ A connected graph with no cycles is disconnected by
  the removal of any edge.
\end{lemma}
\begin{proof}
  By contradiction\.  Suppose we can delete the edge $\{u,v\}$ without
  disconnecting the graph\.  This means there is a path from $u$
  to~$v$ that doesn't use $\{u,v\}$, and thus a simple path\.  Adding
  edge $\{u,v\}$ to a simple path that doesn't use $\{u,v\}$ creates a
  cycle\.  This contradicts the claim of no cycles.
\end{proof}
\begin{lemma} 
  $(2 \implies 3)$
  A connected graph that is disconnected by the removal of any edge has
  a unique simple path between any pair of vertices.
\end{lemma}
\begin{proof}
  Suppose there are two different simple paths from $u$ to~$v$\.  Call
  one $P_1$: $u=x_0,x_1,\ldots,x_k=v$\.  Call the other $P_2$:
  $u=y_0,\ldots,y_l=v$\.  Let $i$ be the smallest such that $x_i \ne
  y_i$ (why does this have to exist?)\.  We claim that we can remove
  $\{y_{i-1},y_i\}$ without disconnecting~$G$\.  To see this, consider
  a pair of vertices $z$ and~$w$\. There's a simple path between them
  at the start\.  It remains to show there's still a path (that doesn't
  need to be simple) after removing $\{y_{i-1},y_i\}$\.  We use proof
  by cases.

  Case 1:  $\{y_{i-1},y_i\}$ wasn't on the path\.  Then the path remains
  after removing $\{y_{i-1},y_i\}$.
  
  Case 2: $\{y_{i-1},y_i\}$ was on the path\.  We can assume that
  $y_{i-1}$ is encountered first\. So the path looked like
  $z,\ldots,y_{i-1},y_i,\ldots,w$\.  So there's a different path: go
  from $z$ to $y_{i-1}$ on the first part of $z$-$w$ path, then from
  $y_{i-1}$ to $u$ on the first part of $P_2$, then from $u$ to $v$ on
  $P_1$, then from $v$ to $y_i$ on the second part of $P_2$, then from
  $y_i$ to $w$ on the second part of the $z$-$w$ path\. The
  construction is illustrated in Fig.~\ref{fig:case2}.
  \begin{figure}
    \centerline{\includegraphics[height=.75in]{figures/notconnected}}
    \caption{Although the edge $\{y_{i-1},y_i\}$ was on the path
      from $z$ to~$w$, there is a path from $z$ to~$w$ also when
      $\{y_{i-1},y_i\}$ has been removed. In the case shown above, the
      path goes from $z$ to~$y_{i-1}$, then to~$u$, then to~$v$ along
      the path $u=x_0,x_1,\ldots,x_{k-1},x_k=v$, then to~$y_i$, and
      finally to~$w$.}
    \label{fig:case2}
  \end{figure}
\end{proof}


\subsection{Counting Tree Edges.  Induction off Leaves}


\begin{definition}
  A \emph{leaf} is a node of degree 1.
\end{definition}
\begin{lemma}
  Any tree with more than one vertex has a leaf.
\end{lemma}
\begin{proof}
  Consider a longest simple path $v_1,\ldots,v_k$ (why does such
  exist?)\.  I claim $v_1$ is a leaf\.  Proof: suppose not\.  Then it has
  a second neighbor $x$\.  Is $x=v_i$ for some $i$?  No, that would
  give a cycle\.  Thus $x,v_1,\ldots,v_k$ is a longer simple path, a
  contradiction.
\end{proof}
The following is ``obvious,'' but I'll write down a proof for those who
want to read it.
\begin{lemma}
  If we remove a leaf and its edge from a tree, we get a tree.
\end{lemma}
\begin{proof}
  Suppose we remove leaf $v$ and its one incident edge $(u,v)$\.  We
  need to show the remaining graph is still connected (it is clearly
  still acyclic)\.  Consider the unique simple path between two other
  vertices $x$ and $y$\.  Can $(u,v)$ be on this path?  No, because
  $(u,v)$ is the only edge incident on $v$, so we would have to
  traverse it twice to enter and leave $v$\.  This would make a
  non-simple path.

  Since $(u,v)$ is not on the path from $x$ to $y$, there is still a
  path after we delete $(u,v)$\.  This is true for all pairs $x$ and
  $y$, so the remaining graph is connected.
\end{proof}
\begin{lemma}
  Any tree on $n$ vertices has $n-1$ edges.
\end{lemma}
\begin{proof}
  (Trivial base case).  Inductive step: Start with an arbitrary tree
  with $n+1$ nodes\.  Remove one node and its incident edge.  By the
  previous lemma, the result is a tree (with $n$ nodes)\.  By the IH,
  this tree has $n-1$ edges\.  So the original tree has $n$ edges\.
\end{proof}
\begin{lemma}
  Any $n$ vertex connected graph $G$ with $n-1$ edges is a tree.
\end{lemma}
\begin{proof}
  We proved earlier that to be connected (have one connected
  component) a graph must have at least $n-1$ edges\.  So if we remove
  any edge from $G$, it becomes disconnected\.  This is one of the
  definitions of a tree.
\end{proof}



\section{Euler Tours}

The Koenigsberg bridge problem: can we cross all seven bridges in the
town of Koenigsberg
exactly once, without repeats, returning to our starting point?
%[[[Could use an improved picture.]]]
\begin{verbatim}

          |    |           |     /
      ----|----|---   -----|----/
     /    |    |   \ /     |  
----<             --X--     
     \    |    |   / \     |
      ----|----|--/   \----|----\
          |    |           |     \

\end{verbatim}
This problem has a graph representation as shown in Figure~\ref{fig:euler} \\

\begin{figure}[htbp]
\centerline{\includegraphics[height=1.5in]{figures/euler}}
\caption{Graph representation for the Koenigsberg bridge problem.}
\label{fig:euler}
\end{figure}

Stated as a general graph theory problem, the problem is to construct
a circuit of the graph that traverses every edge exactly once.  (Each
edge will be traversed in exactly one direction.)  (Actually, note
that the Koenigsberg graph is technically a multigraph, not a simple
graph, because it has multiple edges between two of the pairs of
vertices.  We could change this into a simple graph by adding some
extra vertices in the middle of the repeated edges.)  Euler, in 1736,
proved that it can't be done.  So we call such tours ``Euler Tours.''

\begin{definition}
An Euler tour of an undirected graph $G$ is a circuit that traverses
every edge of $G$ exactly once.
\end{definition}

\begin{theorem}
If undirected graph $G$ has Euler tour, then $G$ is connected and every
vertex has even degree.
\end{theorem}
\begin{proof}
Direct every edge according to tour.  We enter a vertex as many times
as we leave it.  So every vertex must have indegree
equal to outdegree.  So total even.
\end{proof}

It follows that there is no tour of Koenigsberg, because there is an
odd-degree vertex.

100 years later, Hierholzer proved the converse (that's the trouble
with coming second---no one remembers your name!)
\begin{theorem}
If $G$ is connected and every node has even degree, 
then it has an Euler tour.
\end{theorem}

\begin{proof}
  If $G$ has only one node then it has a trivial (1-node) Euler tour.
  So assume $G$ has at least two nodes.  Then $G$ must have at least
  one edge (to be connected).  Starting from this edge, construct a
  circuit with no repeated edges: trace from node to node until we
  cannot go any further on an unused edge.  \forlecture{\bf \\ (do
    example)\\ } Because every node has even degree, this can only
  happen when we return to the node we started at (every other node we
  reach will have another edge by which we may leave).

  Let $C$ be the longest circuit without any repeated edges.  If $C$
  includes all the edges of $G$, we are done.  So assume it doesn't.
  Let $H$ be the subgraph of $G$ consisting of all the edges of $G$
  that aren't in $C$, and all the nodes of $G$ that are incident on
  these edges.  We claim that some node $u$ in $H$ is also in $C$.
  Why?  Because $G$ is connected.

  Now choose any edge of $H$ incident upon $u$.  Starting with that
  edge, construct a cycle in $H$, following the same procedure as
  above.  Eventually, it has to get back to its starting point $u$.
  Now we have two cycles with disjoint edge sets and a common vertex
  $u$.  Splice them together to get a larger cycle than $C$.  The
  contradicts the choice of $C$ as maximum.
\end{proof}

\section{Euler Circuits}

We can generalize Euler tours to directed graphs.  
\begin{definition}
An Euler Circuite of a directed graph $G$ is a circuit in $G$ that
traverses each edge of $G$ exactly once. 
\end{definition}

\begin{figure}[htbp]
\centerline{\includegraphics[height=1.5in]{figures/eulerdigraph}}
\caption{An Euler circuit exists if we add the edge (3,2)}
\label{fig:EulerCir}
\end{figure}

\begin{theorem}
  Suppose $G$ is a weakly connected digraph.  Then $G$ has an Euler
  circuit if and only if the in-degree and out-degree of each vertex
  are equal.
\end{theorem}
\begin{proof}
  We first prove the ``only if'' direction.  Assume $G$ has an Euler
  circuit.  Fix any node $u$.  It occurs some number $k$ of times in
  the circuit.  Each time it occurs, it has one edge in and one edge
  out.  This uses up all the edges of the graph, and no edge is used
  more than once.  So each vertex has equal in-degree and out-degree.

  Now we prove the ``if'' direction: Assume $G$ is a weakly connected
  digraph such that each node's in-degree and out-degree are equal.

  If the edge set is empty, then weak connectivity implies that there
  can be only one node.  That node by itself constitutes a trivial (0
  edge) Euler circuit.  So assume that the edge set is nonempty.

  In this case, we can show that there exists some circuit with no
  repeated edges.  We show this by starting with any edge, and tracing
  from node to node along unused edges, until we reach a node for
  which all its outgoing edges were traced. This is the node we
  started with, since whenever we reach another node the number of
  incoming edges that have been traversed is one larger than the
  number of outgoing edges that have been traversed.

  Now choose a maximum length circuit in $G$ with no repeated edges;
  call it $C$.  If $C$ includes all the edges, we're done.  So assume
  that it doesn't.

  Let $H$ be the subgraph of $G$ consisting of all the edges of $G$
  that aren't in $C$, and all the nodes of $G$ that are incident on
  these edges.  Claim that some node in $H$ is also in $C$.  For if
  not, $G$ is not weakly connected (since we can partition the set of
  nodes to the nodes in $H$ and in $C$ and there is no edge connecting
  these two sets of nodes).  Choose such a node, $u$.

  The fact that $u$ has an incoming or outgoing edge that was not
  traversed, implies that $u$ must have an outgoing edge that was not
  traversed (the number of traversed incoming and outgoing edges must
  be equal).  Starting with that outgoing edge, construct a cycle in
  $H$, following the same procedure as above.  Eventually, it has to
  get back to its starting point.

  Now we have two cycles with disjoint edge sets and a common vertex,
  $u$.  We can splice them together to get a larger cycle than $C$.
  But this contradicts the choice of $C$ as maximum.
\end{proof}



\end{document}

DON'T ERASE---USE FUTURE YEARS





\subsection{Spanning Trees and Forests}

We've just argued that the ``minimal'' connected graphs are trees\.
It turns out that every connected graph actually contains one:
\begin{definition}
  A \emph{spanning tree} of a graph is a subset of the graph edges that
  forms a tree on all the graph nodes.
\end{definition}
Notice that the notion ``tree'' is an intrinsic concept (cares only
about the nodes adjacent to the edges of the tree), while ``spanning
tree'' is extrinsic (cares about whether you have all the graph's
nodes).
\begin{lemma}
  Every connected graph contains a spanning tree.
\end{lemma}
\begin{proof}
  Well-ordering\.  Consider the counterexample with the fewest edges\.
  If you cannot delete any edge and stay connected, it is a tree (3rd
  definition of tree)\.  So you can delete an edge and get a smaller
  counterexample\.  Contradiction.
\end{proof}
Some graphs aren't connected; they don't have spanning trees\.
Instead, they have spanning \emph{forests}:
\begin{definition}
  A \emph{forest} is any acyclic graph.
\end{definition}
\begin{lemma}
  Each connected component of a forest is a tree.
\end{lemma}
\begin{proof}
  Each connected component of a forest is connected and acyclic.
\end{proof}
\begin{definition} 
  A \emph{spanning forest} for a graph $G$ is a forest that connects
  every pair of vertices that were connected in $G$,
\end{definition}
People take some liberties with ``tree:'' they call a set of edges a
tree if it connects its vertices and is acyclic\.  So we talk about a
forest as being ``a collection of trees'' even though each tree is
only on vertices of a connected component, not on all graph vertices\.
In particular, a spanning forest $G$ is just a collection of trees,
one spanning each connected component of $G$.






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Digraphs}

% [[[I have gone through past notes and Rosen, trying to collect
% everything we would like them to know about digraphs.]]]

\subsection{Basic definitions and notation}

We have already defined digraphs: 

A digraph (directed graph) is just the same as a binary relation on a
finite set\.
People don't usually think of it that way, though; when people refer
to a digraph, they are generally thinking of a particular
representation of a binary relation in terms of dots and arrows.
\begin{figure}[b]
  \begin{center}\includegraphics[height=1.5in]{figures/digraph.eps}\end{center}
  \caption{This is a picture of a directed graph or digraph.}
  \label{fig:digraph}
\end{figure}
\forlecture{Recall that a digraph allows self-loops.}
Notation:
$G = (V,E)$, where $V$ is the set of \emph{vertices} and $E$ is the
set of \emph{directed edges}\.
Vertices are sometimes called \emph{nodes}\.
Edges are sometimes called \emph{arcs}\.

A little different from the usual relation notation:
For a relation $R$ on a finite set $A$, we would write 
$G = (V,E)$, where $V = A$, the underlying set, and
$E = R$, the relation, that is the set of ordered pairs $(x,y)$ such
that $x R y$\.

The graphical notation motivates the study of other properties,
especially, properties involving paths and connectivity (see below).

Can also represent digraph by adjacency matrix.

Examples of digraphs we have already seen:
\begin{enumerate}
\item Tournament digraphs (define as special case of digraphs).
\item Precedence digraphs (e.g., for dressing, or prerequisites).
\item The digraphs we studied when we related matrix multiplication to path
  composition.
\end{enumerate}

Some (other) applications:
\begin{description}
\item[Computer network]
A computer network can be modeled nicely as a digraph.  
In this instance, the set of vertices $V$ represents the set of computers in
the network.  An edge $(u, v)$ represents a direct 
communication link from the computer corresponding to $u$ to the
computer corresponding to $v$. 

\item[Airline Connections] 
Here the vertices are airports and edges are flight paths.  
We could indicate the direction that planes fly
along each flight path by using a directed graph.  

\item[Precedence Constraints] Suppose you have a set of jobs to
  complete, but some must be completed before others are begun.  (For
  example, Attila the Hun advised that you should always pillage
  \emph{before} you burn.)  Here the vertices are jobs to be done.
  Directed edges indicate constraints; there is a directed edge from
  job $u$ to job $v$ if job $u$ must be done before job $v$ is begun.

\item[Program Flowchart] Each vertex represents a step of computation.
Directed edges between vertices indicate control flow.
\end{description}

Variants of digraph definition: \\
Could add \emph{weights} $w(u,v)$ to the edges, representing some
kind of cost.
E.g., for airline connections, $w(u,v)$ might be the distance between
airports $u$ and $v$, or the flying time between them, or even the airfare.

Could also use other kinds of \emph{labels}, representing kinds of
relationships between vertices.

\subsection{More definitions}

% p. 446 Rosen, bottom

If $(u,v)$ is an edge of $G$ (element of the edge set $E$ of $G$),
then we call $u$ the \emph{initial vertex} and $v$ the \emph{terminal
vertex} of the edge.

The \emph{in-degree} of $u$ is defined to be the number of edges with
$u$ as terminal vertex. \\
The \emph{out-degree} of $u$ is defined to be the number of edges
with $u$ as initial vertex.

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/digraph.eps,height=1.5in}}
\caption{in-degree of $2$ is 1 out degree of $2$ is 2.}
\label{fig:digraphio}
\end{figure}

\begin{theorem}
Sum of the indegrees of all nodes in a graph 
  = sum of outdegrees of all nodes in the graph 
  = number of edges
\end{theorem}

\begin{proof}
Induction on number of edges.
For the base case consider the graph with no edges
for which the sum of the indegrees is equal to the
sum of the outdegrees, which is $0$.
For the induction step consider a graph with $n+1$ edges,
remove an edge, reducing each of the indegree sum and the 
outdegree sum by $1$. The obtained graph has $n$ edges and 
therefore the induction assumption can be used to conclude 
the theorem.
\end{proof}

\subsection{Paths and connectivity}

\subsubsection{Paths, simple paths, and circuits}

Path in a digraph: 
Same as path in the corresponding binary relation.

In a digraph, a \emph{path} from a vertex $u$ to a vertex $v$ is a
sequence of vertices $u = u_0, u_1, \ldots, u_k = v$ such that each
consecutive pair $(u_i,u_{i+1})$ form an edge of the digraph.
We allow a path of length $0$, which is just a single vertex $u_0$.
The \emph{length} of the path is $k$ (the number of edges).
A path may contain the same edge or vertex multiple times.

% [[[Shlomi:  I prefer the definition of path in terms of vertices, not
% edges.  Also, we should allow the length $0$ path.  OK?  Please
% change for the relations lecture.]]]

This is a little different from Rosen's definition:
there, paths have at least two vertices (one edge).
%[[[The one I've used is, I think, reasonably standard.  Needs
%checking.  It seems much neater to me.]]]
Our definition is consistent, for example, with the Cormen,
Leiserson, Rivest textbook used in 6.046.

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/digraph.eps,height=1.5in}}
\caption{$u= 1,2,1,2,4,3$ is a path of length 5}
\label{fig:digraphpa}
\end{figure}

A path is \emph{simple} if no vertex appears more than once, 
with the possible exception that the first vertex may be the same as
the last. 
In other words, $u_0, u_1, u_2, \ldots, u_{k-1}$ are all distinct
vertices, and $u_1, u_2, \ldots, u_k$ are all distinct vertices,
but $u_0 = u_k$ is permitted.

The path $2,1,2$ of the digraph in Figure \ref{fig:digraphpa}
is simple, while the path $2,1,2,4$ is not simple.

Again, this definition is different from the one used in Rosen:
he defines ``simple'' to mean ``no repeated edges''.
%[[[The one I've used is, I think, reasonably standard.  Needs
%checking.  It seems much neater to me.]]]

\begin{theorem}
If $|V| = n$, then any simple path has length at most $n$.
\end{theorem}

The only case where the length is actually $n$ is a simple cycle
involving all the nodes.

\begin{theorem}
If $|V| = n$, and there is a path from $u$ to $v$ in $G$, then there
is a simple path from $u$ to $v$.
\end{theorem}

\begin{proof}
  Consider a shortest path from $u$ to $v$ (this uses the
  well ordering principle, so is really induction).  Suppose it is not
  a simple path---so some vertex is repeated.  So the path has the
  form $u_0,\ldots,u_i,\ldots,u_j,\ldots,u_k$ where $u_i=u_j$.  But
  then $u_0,\ldots,u_i,u_{j+1},\ldots,u_k$ is a shorter path, a
  contradiction.
\end{proof}

(Actually, we can always get a simple path of length at most $n-1$.
because the special case of a simple cycle involving all the nodes can
be reduced to a trivial length $0$ path.)

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/digraph.eps,height=1.5in}}
\caption{$u= 1,2,1,2,4,3$ can be shortened to the simple path $1,2,4,3$}
\label{fig:digraphsp}
\end{figure}

\emph{Circuit} (also known as a \emph{cycle}) 
is a path that begins and ends at the same vertex.
(Usually, the degenerate case of a one-node, length $0$ path is not
considered to be a circuit, but we won't exclude it---will have to
take care of boundary cases in proofs, though.)

%[[[David defined a cycle to be a simple circuit.  But Rosen has the
%two terms equivalent.  I suggest that we used them as Rosen does, and
%say ``simple circuit'' or ``simple cycle'' when we want to talk about
%no revisiting vertices.]]]

%Examples -- we have an example above

\subsubsection{Paths and relational operations}

Main results, (mainly review from relations, restated in digraph notation):
Let $G = (V,E)$. 
\begin{itemize}
\item
There is a path of length $k$ from $u$ to $v$ in $G$ if and
only if $(u,v) \in E^k$.
($E$ is the relation corresponding to the edges.)
\item
There is a path from $u$ to $v$ in $G$ if and only
if $(u,v)$ is in the reflexive transitive closure of $E$.
(In this case, we say that $u$ is \emph{connected to} $v$ in $G$.)
\end{itemize}

Recall/review how the adjacency matrix representation can be used to calculate
the needed products and take the needed closures.

Can also use this representation to calculate the number of paths
between all pairs of vertices.
%Do Rosen p. 472, Theorem 2 and its proof?
% [[[Or do this for HW?]]]

%Examples
\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/fall00/newlectures/digraphcir.eps,height=1.5in}}
\caption{Number of paths in digraphs}
\label{fig:NPdigraphs}
\end{figure}

The $R$ matrix:

\[\begin{array} {r|cccc}
 &1& 2&  3& 4 \\ 
\hline
1&0& 1&  0& 0 \\
2&1& 1&  0& 1 \\
3&0& 0&  1& 0 \\
4&0& 0&  1& 0 \\
\end{array}\]

$R^2$ matrix:

\[\begin{array} {r|cccc}
 &1& 2&  3& 4 \\ 
\hline
1&1& 1&  0& 1 \\
2&1& 2&  1& 1 \\
3&0& 0&  1& 0 \\
4&0& 0&  1& 0 \\
\end{array}\]

$2,2,2$ (self-loops) and $2,1,2$ are the two paths from 2 to
itself.

$R^3$ matrix:

\[\begin{array} {r|cccc}
 &1& 2&  3& 4 \\ 
\hline
1&1& 2&  1& 1 \\
2&2& 3&  2& 2 \\
3&0& 0&  1& 0 \\
4&0& 0&  1& 0 \\
\end{array}\]

For example, $2,2,2,2$, $2,1,2,2$, and $2,2,1,2$ are the three paths
from $2$ to itself. 

\subsubsection{Strong and Weak connectivity}

\begin{definition}
Digraph $G$ is \emph{strongly connected} if there is
a path from every vertex to every other vertex.
\end{definition}

\begin{definition}
Digraph $G$ is \emph{weakly connected} if it is possible to
get from every vertex to every other vertex by following digraph edges
\emph{in either the forward or backward direction}. 
\end{definition}

Examples of digraphs that are and aren't strongly connected.
%[[[draw]]]

Digraphs can be subdivided into strongly connected components.
These may be disconnected, or may be connected to each other with
one-way edges.
%[[[example]]]


\section{Undirected Graphs}

Some relations, in particular, those that are symmetric but not
reflexive, have nice representations using a different kind of
graph, called an \emph{undirected graph}, or just a \emph{graph}.

\subsection{Simple graphs}

Start with a symmetric, irreflexive relation.
In a symmetric relation, if edge $(u,v)$ is present, edge $(v,u)$ is
also present.  
In an irreflexive relation, no edge $(u,u)$ is present.

A digraph representing such a relation has the following properties:
\begin{enumerate}
\item
No self-loops.
\item
Edges come in pairs:  wherever there is an edge from $u$ to $v$, there
is another edge from $v$ to $u$.
\end{enumerate}
Because edges come in pairs, it simplifies matters to think of these
two edges as one ``undirected edge''.
An undirected graph is defined formally to be a structure that
consists of vertices and undirected edges:

Definition:
An undirected \emph{graph}, also known as just a \emph{graph},
is a pair of sets $(V, E)$.  
The elements of $V$ are called \emph{vertices}.  
The elements of $E$ are called \emph{edges}.
Each edge is an unordered pair of distinct vertices.

Graphs can be nicely represented with a diagram of dots and lines (not
arrows), as shown in Figure~\ref{fig:graph}
\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/graph.eps,height=1.5in}}
\caption{This is a picture of a graph $G = (V, E)$.  There are four
vertices and four edges.  The set of vertices $V$ is $\{1, 2, 3, 4\}$.
The set of edges $E$ is $\{(1,2), (1,3), (2,3), (3,4) \}$.  Vertex 1
is adjacent to vertex 2, but is not adjacent to vertex 4.}
\label{fig:graph}
\end{figure}

As noted in the definition, each edge $(u,v) \in E$ is a pair of
distinct vertices $u, v \in V$.  
Because it's an unordered pair, we really shouldn't be writing it
using Cartesian pair notation (because order matters in that
notation).
Really picky mathematicians denote such an unordered edge by the
unordered \emph{set} $\set{u,v}$.
But this rapidly fills up your paper with hard to read $\set{}$ symbols.
So most people are a little casual here and use the ordered notation
even though it's an unordered pair.

Edge $(u, v)$ is said to be \emph{incident} to vertices $u$ and $v$.  
Vertices $u$ and $v$ are said to be \emph{adjacent} or \emph{neighbors}.  
Phrases like, ``an edge joins $u$ and $v$'' and ``the edge between $u$
and $v$'' are common.

Example:
Computer networks are often modeled nicely as undirected graphs,
because most communication links are bidirectional.
The set of vertices $V$ represents the set of computers in
the network.  There is an edge $(u, v)$ if there is a direct
communication link between the computers corresponding to $u$ and $v$.

\subsection{Not-So-Simple Graphs}

The definition in the preceding section only describes \emph{simple
undirected graphs}.  There are many ways to complicate matters.

\subsubsection{Multigraphs}

In a simple graph, there are either zero or one edges joining a pair
of vertices.  In a \emph{multigraph}, multiple edges are permitted
between the same pair of vertices.

\subsubsection{Pseudographs}
%[[[Rosen uses the term ``pseodograph'' for this.]]]

In a simple graph or multigraph, each edge is a pair of distinct
vertices.  A \emph{self-loop} is an edge that connects a vertex to itself.
A \emph{pseudograph} allows multiple edges and self-loops.
Figure~\ref{fig:multigraph} depicts a pseudograph.

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/multigraph.eps,height=1.5in}}
\caption{This is a picture of a multigraph with a self-loop.  In
particular, there are three edges connecting vertices 1 and 2 and there
is a self-loop on vertex 3.}
\label{fig:multigraph}
\end{figure}

\subsubsection{Weighted Graphs}

Sometimes it is useful to associate a number with each edge in a
graph.  These numbers are usually called \emph{weights}.  The weight of
an edge $(u, v)$ is often denoted $w(u, v)$.  (If there is no edge
between vertices $u$ and $v$, then often $w(u, v)$ is taken to be a
default value, like infinity or zero.)

Recall that an ordinary graph can be represented nicely by an 
\emph{adjacency matrix}. 
Because the underlying relation for an undirected graph is symmetric,
such a matrix is symmetric around the main diagonal.
Also, because the underlying relation is irreflexive, the main
diagonal consists of all $0$s.

Some variants of simple graphs can also be described well by matrices.
For example, a weighted graph is naturally represented by a matrix
where $w(u,v)$ is the entry at row $u$ and column $v$.

\subsection{Standard Types of Graphs}

Some graphs appear so frequently that they have names.  The most
important examples are shown in Figure~\ref{fig:zoo}.

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/zoo.eps,height=3.0in}}
\caption{The types of graph shown here are so common that they
have names.  (a) The empty graph on five vertices, $E_5$.  An empty
graph has no edges at all.  (b) The cycle on five vertices, $C_5$.
(c) The complete graph on five vertices, $K_5$.  A complete graph has
an edge between every pair of vertices.  (d) A five-vertex line graph.
(e) A $5 \times 5$ 2-dimensional mesh.}
\label{fig:zoo}
\end{figure}

\subsection{More definitions}

\subsubsection{Subgraphs}

A \emph{subgraph} of a graph $G = (V, E)$ is a graph $G' = (V' , E')$
such that $V' \subseteq V$ and $E' \subseteq E$.  For example, a
triangle is a subgraph of $K_4$ (the complete graph on four vertices),
but not of $C_4$ (a cycle with four vertices).

%[[[Need similar definition for digraphs, earlier.]]]

\subsubsection{Vertex degree}

The \emph{degree} of a vertex is the number of incident edges.  The
degree of vertex $v$ is often denoted $d(v)$.  For example, referring
to Figure~\ref{fig:zoo}, every vertex in an empty graph has degree 0,
but every vertex in a cycle has degree 2.  A look at the other
examples suggests the following theorem:

\begin{theorem}
In a graph with $m$ edges, the sum of degrees of the vertices is $2m$.
\end{theorem}

\begin{proof}
  By induction on the number of edges.  0 edges means the sum is 0 as
  claimed.  Consider an $m+1$-edge graph.  Take away one of the edges.
  The remaining graph has degree sum $2m$ (by induction).  Putting
  back the edge increments two degrees by one, so the degree sum 
  becomes $2(m+1)$.
\end{proof}

\begin{corollary}
In every graph, there are an even number of vertices of odd degree.
\end{corollary}

\begin{proof}
  If we had an odd number of odd degrees, the degree sum would be
  odd.  But it is even.
\end{proof}

% 3:35 ?

% [[[got here in lecture]]]


\section{Graph Coloring}

Time to discuss final exams.  The MIT Schedules Office needs to assign
a time slot for each final.  This is not easy, because some students
are taking several classes with finals, and a student can take only
one test during a particular time slot.  The Schedules Office wants to
avoid all conflicts, but wants to make the exam period as short as
possible.

This scheduling problem can be represented by a graph.  Let each
vertex represent a course.  Put an edge between two vertices if there
is some student that is taking both courses.  Identify each possible
time slot with a color.  For example, Monday 9-12 is red, Monday 1-4
is blue, Tuesday 9-12 is green, etc.  The problem of assigning time
slots to exams is then equivalent to the problem of assigning colors
to vertices.

If a student is taking two courses, then there is an edge between two
vertices.  If these vertices are the same color, then there is a
conflict because the student has to take exams for the two courses at
the same time.  Therefore, the problem is to color each vertex of the
graph so that no adjacent vertices have the same color and so that the
number of colors used is as small as possible.  An example is shown in
Figure~\ref{fig:exams}.

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/exams.eps,height=2in}}
\caption{This graph represents the exam scheduling problem.  Each
vertex stands for a course.  An edge between two vertices indicates
that a student is taking both courses and therefore the exams can not
be scheduled at the same time.  Each exam time slot is associated with
a color.  A schedule that creates no conflicts corresponds to a
coloring of the vertices such that no adjacent vertices receive the
same color.}
\label{fig:exams}
\end{figure}

In general, the minimum number of colors needed to color the vertices
of a graph $G$ so that no two adjacent vertices are the same is called
the \emph{chromatic number} and is written $\chi(G)$\footnote{This is
the Greek letter ``chi'' pronounced ``key'' by the ancient Greeks and
``kie'' by mathematicians and frats.}.  For example, if $G$ is the
3-cycle or triangle graph, then $\chi(G) = 3$.

In general, finding the chromatic number of a graph is very hard.
However, we can at least put some upper bounds on the chromatic
number.  For example, the chromatic number of an $n$-vertex graph is
certainly at most $n$, since every vertex could be assigned a
different color.

We can do better, however:
\begin{theorem}
Any graph in which the maximum vertex degree is $\Delta$ can be
colored with at most $\Delta+1$ colors.
\end{theorem}

This theorem implies, for example, that a graph with thousands of
vertices, each of degree 3, requires at most 4 colors.  The proof is
surprisingly easy:

\begin{proof}
  The proof is by induction.  Let $P(n)$ be the proposition that every
  graph with $n$ vertices, all with degree at most $\Delta$, can be
  colored using at most $\Delta + 1$ colors.

  For the base case, $P(1)$, we consider a single vertex with degree
  zero.  In this case, $\Delta = 0$ and the algorithm requires $ 1 \le
  \Delta+1$ colors.

  In the inductive step, assume $P(n)$ to prove $P(n+1)$.  Let $G'$ be
  the graph obtained from $G$ by removing a vertex $v$ and incident
  edges.  No vertex in $G'$ has degree greater than $\Delta$, since
  removing a vertex and incident edges can not increase the degree of
  any other vertex.  By induction, we can color $G'$ with at most
  $\Delta + 1$ colors.  

  Now we need to ``put back'' the vertex $v$ we removed and color it.
  But $v$ has at most $\Delta$ neighbors in $G$.  Among them, these
  other vertices can ``use up'' at most $\Delta$ colors.  Thus, one of
  our $\Delta+1$ candidate colors is still available to color the
  replaced vertex without violating the coloring rules.
\end{proof}

% 3:45



\section{Connectivity}

Is a graph all in one piece or composed of several pieces?  To walk
from one vertex to another, how many edges must one cross?  Are there
many different routes or just one?  These are questions about
connectivity.

\subsection{Basic Notions of Connectivity}

Definitions similar to those for digraphs.

In a graph, a \emph{path} from a vertex $u$ to a vertex $v$ is a
sequence of vertices $u = u_0, u_1, u_2, \ldots, u_k = v$, where each
$(u_i,u_{i+1})$ is an edge of the graph.
A path may contain the same edge or vertex multiple times.

In a \emph{simple path}, no vertex appears more than once.
However, as a special case, the initial and final vertices may be the
same.  In other words, $u_0, u_1, u_2, \ldots, u_{k-1}$ are all distinct
vertices, and $u_1, u_2, \ldots, u_k$ are all distinct vertices,
but $u_0 = u_k$ is permitted.

Because we are working with undirected graphs,
there is a path from $u$ to $v$ iff there is a path from $v$ to $u$;
one path is obtained from the other by reversing the sequence of
edges.  The same statement holds for simple paths.

A \emph{circuit}, or \emph{cycle} is a path from a vertex back to
itself, i.e. a path $u = u_0, u_1, u_2, \ldots, u_k = v$ where $u =
u_0 = u_k = v$.
%A \emph{cycle} is a simple path from a vertex back to itself.  
%Thus, a path is to a circuit as a simple path is to a cycle; both of
%the former may contain the same edge or vertex multiple times, but
%this is ruled-out in the latter.

We say two vertices are \emph{connected} if there is a path between
them.
\begin{lemma}
  There is a path between two vertices iff there is a simple path
  between them.
\end{lemma}
So we could equally well say connected means there is a simple path between
them.

\begin{proof}
Like the analogous proof for the digraph case. 
\end{proof}

A graph is \emph{connected} if there is a path between every pair of
distinct vertices.  For example, referring back to
Figure~\ref{fig:zoo}, the empty graph is disconnected, but all others
shown are connected.

\begin{theorem}
In any undirected graph, connectedness is an equivalence relation.
\end{theorem}

\begin{proof}
It is reflexive because we allow length $0$ paths.
It is symmetric because we can reverse paths in an undirected graph.  
It is transitive because we can concatenate paths.
\end{proof}

Like any equivalence relation, connectedness induces a partition of
the vertices into equivalence classes.  Each equivalence class is
called a \emph{connected component}.  A connected component is a set of vertices
each of which can reach all the others, and none of which can 
reach any other vertices.

We can also say that a connected component of a graph is a subgraph
that is connected and maximal.  This is, if any more vertices are
added to the subgraph, then it is no longer connected.  For example,
every connected graph has exactly one connected component.  The empty
graph on $n$ vertices has $n$ connected components.  A graph with
three connected components is shown in Figure~\ref{fig:3comp}.

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/3comp.eps,height=1.5in}}
\caption{This is a picture of a graph with 3 connected components.}
\label{fig:3comp}
\end{figure}

\subsection{Cuts}

Another way to look at connectivity is to see what prevents it.
\begin{definition}
A \emph{cut} in a graph $G = (V,E)$ is a partition of the vertices
$V$ into two nonempty sets $W$ and $V - W$. \\
A cut is said to be \emph{empty} provided that no edge of $G$
connects $W$ and $V - W$, that is, no edge has one endpoint in each set.
\end{definition}

\begin{theorem}
A graph is connected iff it has no empty cuts.
\end{theorem}
\begin{proof}
Show the equivalent proposition: a graph is disconnected iff it has an
empty cut. \\
\\
Suppose $G$ has an empty cut $(W,V-W)$.  \\
Let $w \in W$ and $v \in V-W $.  \\
We show that there is no path from $v$ to $w$, 
which implies that $G$ is not connected.  \\
We proceed by contradiction: 
suppose there is a path $v=p_0,\ldots,p_k=w$ from $v$ to $w$.  \\
Consider the smallest $j$ such that $p_j \in W$. \\
(This is using the well ordering principle:
the set of $j$ such that $p_j \in W$ is nonempty since $k$ is in the
set, so it has a smallest element $j$).  \\
Note $j\ne 0$, so $p_{j-1}$
is a vertex on the path that is not in $W$.  So the edge
$(p_{j-1},p_j)$ has one endpoint in $W$ and the other in $V-W$,
contradicting the claim that $(W,V-W)$ is an empty cut. \\
\\
For the other direction, suppose that $G$ is disconnected and construct an
empty cut.  \\
By assumption, there is a pair of vertices $v$ and $w$
such that there is no path from $v$ to $w$. \\
Let $W$ be the set of vertices connected to $w$ (by a path).  \\
Then $(W,V-W)$ is an empty cut. \\
For suppose the cut is not empty. \\
Then there is an edge $(x,y)$ with $x\in W$ and $y \in V-W$. \\
But there is a path from $w$ to $x$. \\
Adding the edge $(x,y)$ gives a path from $w$ to $y$, so $y \in W$. \\
This is a contradiction.
\end{proof}

\subsection{A False Theorem about Connectivity}

If a graph is connected, then every vertex must be connected to some
other vertex.  Is the converse of this statement true?  If every
vertex is connected to some other vertex, then is the graph connected?
The answer is no.  In fact, the graph with three connected components
showing in Figure~\ref{fig:3comp} is a counterexample.  So what is wrong
with the following proof?

\begin{falsethm}
If every vertex in a graph with at least $2$ nodes is adjacent to
another vertex, then the graph is connected.
\end{falsethm}

Nothing helps a false proof like a good picture; see
Figure~\ref{fig:false}.

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/false.eps,height=1.5in}}
\caption{This picture accompanies the false proof.  Two situations
are depicted.  In one, vertices $x_1$ and $x_2$ both lie among the
first $n$ vertices, and so there is a connecting path by induction.
In the second, $v = x_1$ and $x_2$ is among the first $n$ vertices.
In this case there is a connecting path because there is an edge from
$v$ to $u$ and a path from $u$ to $x_2$ by induction.}
\label{fig:false}
\end{figure}

\begin{proof}
The proof is by induction.  Let $P(n)$ be the predicate that if every
vertex in an $n$-vertex graph is adjacent to another vertex, then the
graph is connected.  In the base case, $P(2)$ is trivially true.

In the inductive step, we assume $P(n)$ to prove $P(n+1)$.  Start with
an $n$-vertex graph; this is connected by induction.  Now add a vertex
$v$.  By assumption $v$ is connected to one of the first $n$ vertices;
call that one $u$.

Now we must show that for every pair of distinct vertices $x_1$ and
$x_2$, there is a path between them.  If both $x_1$ and $x_2$ are
among the first $n$ vertices, then there is a path by induction.
Otherwise, one of the vertices is $v$ (say $x_1$) and the other is
among the first $n$ vertices.  These are connected by the path from
$x_1$ to $u$ to $x_2$ as shown in the figure.
\end{proof}

The error is in the early statement ``Start with an $n$-vertex graph;
this is connected by induction.''  The induction hypothesis does not
say that every $n$-vertex graph is connected, but only, ``\emph{if
every vertex in an $n$-vertex graph is adjacent to another vertex,}
then the graph is connected''.

The core problem here is called ``buildup error'' and is a common
source of mistakes in inductive proofs.

The name buildup error arises from the intuition that usually drives
the error: that in order to create an instance of size $n+1$, you take
an instance of size $n$ and extend it by one.  If you are careless,
you can forget some of the possible ways a size $n+1$ problem can
arise: you fail to ``build'' all the size $n+1$ instances, so your
proof doesn't cover all the instances.

More formally, buildup error occurs when the induction hypothesis
$P(n)$ is itself an implication of the form $A \Rightarrow B$.
%[[[Actually, it should be ``for all $G$ with $n$ nodes, $A(G)
%\Rightarrow B(G)$''.]]]
In this instance, $A$ is the statement, ``every vertex is adjacent to
another vertex'' and $B$ is the statement, ``the graph is connected''.

In the inductive step of a correct proof, we assume $A \Rightarrow
B$ for $n$ in order to prove $A \Rightarrow B$ for $n+1$.  In an erroneous
proof, we assume $B$ for $n$ in order to prove $A \Rightarrow B$ for $n+1$.
This is precisely what happened; we assumed, ``the graph is
connected'' rather than, ``if every vertex is
adjacent to another vertex, then the graph is connected''.

\subsection{Number of Connected Components}

Now a true theorem about connectivity...

We start with the common-sense observation that if a graph has too few 
edges, it cannot contain a path between every pair of vertices.  
More generally, a graph with a very small
number of edges ought to have many connected components.  (Remember,
``many connected components'' does not mean ``very connected'';
rather, it means ``broken into many pieces''!)  The following theorem
makes these observations concrete. 

\begin{theorem}
A graph with $k$ edges and $n$ vertices, where $n$ and $k$ are natural
numbers, has at least $n - k$ connected components.
\end{theorem}

For example, a graph with $0$ edges and $20$ vertices has at least $20 - 0
= 20$ connected components.\\
A graph with 100 vertices and 35 edges must have at least 100 - 35 =
65 connected components. \\
A graph with 35 vertices and 100 edges must have at least 35 - 100 =
-65 connected components. \\
(True, but not very interesting.) \\
\\
The theorem is proved by fixing any generic $n$, and then working by
induction on $k$. \\
This may seem odd, because for $k > n$, the theorem says that the
number of connected components is greater than some negative number.\\
This is useless, but true, so there is no harm.

\begin{proof}
Fix $n$. 
The proof is by induction on $k$, starting from $k = 0$. \\
\\
Let $P(k)$ be the predicate that an $n$-vertex graph with $k$ edges
has at least $n - k$ connected components.  In the base case, $P(0)$
holds because an $n$-vertex graph with 0 edges does have at least $n -
0 = n$ components. \\
\\
For the inductive step, assume that an $n$-vertex graph with $k$ edges
has at least $n - k$ connected components, and try to prove that an $n$-vertex
graph with $k + 1$ edges has at least $n - k - 1$ connected
components. \\
Let $G$ be a graph with $n$ vertices and $k + 1$ edges. \\
Remove one edge $e$, which gives a subgraph $G'$. \\
The resulting graph $G'$ has $n$ vertices and $k$ edges.  \\
By inductive hypothesis, this graph $G'$ has at least $n - k$
connected components. \\
\\
Now consider what happens to the number of connected components when
we add the edge $e$ back in. \\
There are two possibilities: $e$ may be incident on two vertices
in the same connected component of $G'$, or two vertices in different
connected components of $G'$. \\
\\
In the first case, where $e$ is incident on two vertices in the same connected
component, then the number of connected components is unchanged when
$e$ is added back in, that is, $G$ has at least $n - k$ connected
components in this case. \\
\\
In the second case, where $e$ is incident on vertices in two different 
connected components of $G'$, the two become a single connected
component when $e$ is added back in. \\
This reduces the number of connected components by exactly one, which
implies that there are still at least $n - k - 1$ connected components
in $G$. \\
\\
In both cases, the number of connected components is at least $n - k -
1$, which is what we need to show. 
\end{proof}
If a graph has fewer than $n-1$ edges, then the theorem implies it has
more than one connected component.  Therefore, a graph must have at
least $n-1$ edges to be connected.  In fact, there are graphs with $n
- 1$ edges and a single connected component; the line graph of
Figure~\ref{fig:zoo} is an example. \\
\\
Is this a complete proof?  
Not quite.  We claimed that adding one edge
between two separate connected components 
reduces the number of connected components by one.  This is obvious by
picture, but how do we prove it formally?  
\begin{lemma}
If an edge is added that connects two distinct components of a graph,
the number of components is reduced by one.
\end{lemma}

\begin{proof}
Suppose the added edge is $(v,w)$, and let $[v]$ and $[w]$ be the
connected components containing $v$ and $w$ respectively.  We claim
that upon adding edge $(v,w)$, we merge $[v]$ and $[w]$ into a single
component and affect no other components. \\
\\
To see that no other component is changed, suppose for contradiction
that there is some vertex $q$ \emph{not} in the component of $v$ or $w$
for which adding $(v,w)$ changes its component--that is, the set of
vertices it can reach.  There must be a new path from $q$ to some
other vertex $r$.  The only way this path can be ``new'' is if it uses
edge $(v,w)$.  So both of $v$ and $w$ are on the path from $q$ to $r$.
Suppose without loss of generality that $v$ appears first on the path.
Then there is a path from $q$ to $v$ that does not use edge $(v,w)$.
This path existed before we added $(v,w)$, meaning that $q$ is in the
same component as $v$.  This contradicts our initial assumption.
\end{proof}

\begin{corollary}
Deleting a graph edge increases the number of components by at most
one.
\end{corollary}

\begin{proof}
  Suppose deleting edge $e$ increased the number by more than one.  We
  have just seen that putting $e$ back can \emph{decrease} the number
  of components by at most one.  So deleting $e$ and putting it back
  would give a net gain in the number of components!  This is a
  contradiction.
\end{proof}

% 3:00

% 3:10

\section{Hamiltonian Circuits}

A slightly different question: is there a simple circuit that traverses every
\emph{vertex} exactly once? \\
Such a circuit is called a \emph{Hamiltonian circuit} (Hamiltonian
cycle). \\
Similarly, a simple path that traverses every vertex exactly
once is a \emph{Hamiltonian path}. \\
\\
Small change from the Euler circuit question, but suddenly, instead of
answer being trivial, it becomes very complicated.  \\
It is believed that there is no simple criterion to determine whether
or not a graph has a Hamiltonian circuit;
in fact, it is believed that no computer program can answer
this question efficiently (it is NP-complete). \\
\\
The book has some simple criteria for existence and nonexistence of
Hamiltonian cycles. 
Here is a slightly harder result. 

\begin{lemma}
Any graph with $n$ vertices, $n \geq 3$, in which the minimum degree
of each node is at least $n/2$, has a Hamiltonian circuit.
\end{lemma}

%[[[The proof in last semester's notes was wrong, because it assumed
%that the new vertex's neighbors all had to be on the cycle.  
%This one comes from Bondy and Murty, p. 54-55.]]]

\begin{proof}
By contradiction. \\
Suppose some graph has $n$ vertices, $n \geq 3$, and the minimum degree
of each node is at least $n/2$, but that graph does not have a
Hamiltonian circuit. \\
If we add edges to this graph one at a time, we eventually end up with
a complete graph, which does have a Hamiltonian circuit. \\
(Why?) \\
Somewhere in the process of adding edges, we have a graph $G$ 
that doesn't have a Hamiltonian circuit, but adding one more edge
$(u,v)$ yields a graph $G'$ that does have a Hamiltonian circuit. \\
We'll get a contradiction for this $G$. \\
\\
Since $G$ plus the one edge $(u,v)$ has a Hamiltonian circuit, $G$
alone has a Hamiltonian path from $u$ to $v$ (just remove the one new
edge). \\
Write $u = u_1,\ldots, u_n = v$, includes all the nodes of $G$. \\
\\
Now let's play with that path and turn it into a circuit, to get a
contradiction. \\
We will use the fact that $u$ and $v$ each have degree at least $n/2$
to produce two edges to replace one edge $(u_i,u_{i+1})$ on the
path... \\


\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/fall00/newlectures/figures/hamiltonian.eps,height=2in}}
\caption{Converting the Hamiltonian path into a circuit}
\label{fig:hamiltonian}
\end{figure}

Now let's count:
Of the $n-2$ intermediate nodes on the path 
$u_2,\ldots,u_{n-1}$ (all but the first and last) we know that at
least $n/2$ are neighbors of $u$, and at least $n/2$ are neighbors of $v$. \\
So it can be shown that there are two adjacent nodes, $u_i$ and
$u_{i+1}$, where $u_i$ is a neighbor of $v$ and $u_{i+1}$ is a
neighbor or $u$. \\
Postpone this for a minute... \\
Then cut and add edges, to produce a Hamiltonian circuit,
contradiction. \\
\\
Now, how do we get $u_i$ and $u_{i+1}$? \\
Just count how many are in various sets.  Use a little trick: \\
Let $S$ be $\{ i: u_{i+1} \mbox{ is a neighbor of } u \}$. \\
Let $T$ be $\{ i: u_i \mbox{ is a neighbor of } v \}$. \\
Each of $S$ and $T$ has at least $n/2$ elements.
Since there are only $n-2$ possible values of $i$, some $i$ must be in
both sets. \\
That is, $u_i$ is a neighbor of $v$ and $u_{i+1}$ is a neighbor of $u$.
\end{proof}

This gives a special class of graphs with Hamiltonian circuits.
But no one has nice criteria for finding Hamiltonian circuits in
general, or for determining if they exist. 

% 3:20

\section{Trees}

Important special type of graph for CS applications. \\
Trees are the ``smallest'' connected graphs, in the sense that they
have the fewest edges required for connectivity. \\
We will provide definitions and basic properties, including looking at
some alternative definitions and showing they are equivalent. \\
\\
We will count numbers of vertices and edges. \\
\\
We will relate trees to graphs, by talking about spanning trees and
spanning forests. \\
\\
We will show some places where trees are used in computer science:  
Decision trees, binary search trees, parse trees, tree-structured file
systems,... \\

\subsection{Basic definitions}

\begin{definition}
A \emph{tree} is a connected (undirected) graph with no simple circuits
of length $> 2$.
\end{definition}

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/tree.eps,height=2.0in}}
\caption{ This tree has 11
  ``leaves'', which are defined as vertices of degree at most one.
  The remaining 7 vertices are called ``internal nodes''.}
\label{fig:tree}
\end{figure}

The vertices in a tree can be classified into two categories.
Vertices of degree at most one are called \emph{leaves}, and vertices
of degree greater than one are called \emph{internal nodes}. \\

%Trees are usually drawn as in Figure~\ref{fig:tree} with the leaves on
%the bottom.  Keep this convention in mind; otherwise, phrases like
%``all the vertices \emph{below}...'' will be confusing.
%\forstudent{(The English mathematician Littlewood once remarked that
%  he found such directional terms particularly bothersome, since he
%  habitually read mathematics reclined on his back!)}

Trees can be defined several different ways, as the following lemma shows.
\begin{lemma}
The following properties of a graph $G$ are equivalent (each implies
the others):
\begin{enumerate}
\item $G$ is a connected graph with no simple circuits of length $>2$ 
(a tree, as defined above). 
\item $G$ is a connected graph that is disconnected by the removal of any
  edge, i.e., a ``minimal'' connected graph.
\item $G$ is a graph with a unique simple path between every pair of distinct
  vertices.
\end{enumerate}
\end{lemma}
Since the definitions are equivalent, any one of them could be
taken as the definition of a tree. \\
Theorems asserting that several mathematical statements are equivalent
are quite common.  One way to prove such a theorem would be to
consider every pair of statements in turn and prove them equivalent.
That is, we would prove $1 \Leftrightarrow 2$, $2 \Leftrightarrow 3$,
and $3 \Leftrightarrow 1$. \\
This would be overkill. \\
A simpler approach is to show $1 \Rightarrow 2$, $2
\Rightarrow 3$, and $3 \Rightarrow 1$.  These three implications are
sufficient to prove every pair of statements equivalent.  For example,
$2 \Leftrightarrow 3$ follows because we prove $2 \Rightarrow 3$
directly, and prove $3 \Rightarrow 2$ with the two steps $3
\Rightarrow 1 \Rightarrow 2$.

\begin{lemma}
$(1\implies 2)$ A connected graph with no simple circuits of length
$>2$ is disconnected by the removal of any edge.
\end{lemma}

\begin{proof}
By contradiction.  Suppose we can delete edge $(u,v)$ without
disconnecting the graph.  This means there is a path from $u$ to $v$
that doesn't use $(u,v)$.
Therefore, there is a simple path from $u$ to $v$ that doesn't use
$(u,v)$.
Adding edge $(u,v)$ to this simple path creates a simple circuit.
This contradicts the claim of no simple circuits.
\end{proof}

\begin{lemma}
$(3 \implies 1)$ A graph with a unique simple path between any pair of
nodes is connected and has no simple circuits of length $> 2$.
\end{lemma}

\begin{proof}
It clearly meets the definition of connectivity.  To see there are
no simple circuits we argue by contradiction.  \\
Suppose we have a simple circuit $v_1,v_2,\ldots,v_k,v_1$ of length $>2$.\\
Then there are 2 simple paths from
$v_1$ to $v_k$, namely $v_1,\ldots,v_k$ and the edge $(v_1,v_k)$.
\end{proof}

\begin{lemma} 
$(2 \implies 3)$
A connected graph that is disconnected by the removal of any edge has
a unique simple path between any pair of vertices.
\end{lemma}
\begin{proof}
We prove the contrapositive.
Suppose there are two different simple paths from $u$ to $v$.  \\
Call one $P_1$: $u=x_0,x_1,\ldots,x_k=v$.  \\
Call the other $P_2$:  $u=y_0,\ldots,y_l=v$. \\
Let $i$ be the smallest such that $x_i \ne y_i$ 
(why does this have to exist?). \\
Claim: we can remove the edge $(y_{i-1},y_i)$ without disconnecting
$G$.  \\
To see this, consider any pair of vertices $z$ and $w$. \\
There's a simple path between them at the start. 
It remains to show there's still a path (doesn't need to be simple) 
after removing $(y_{i-1},y_i)$.  We use proof by cases. \\
\\
Case 1:  $(y_{i-1},y_i)$ wasn't on the path.  Then the path remains
after removing $(y_{i-1},y_i)$. \\
\\
Case 2: $(y_{i-1},y_i)$ was on the path.  
WLOG, $y_{i-1}$ is encountered first. \\
So the path looked like $z,\ldots,y_{i-1},y_i,\ldots,w$. \\
So there's a different path: go from $z$ to $y_{i-1}$ on the first
part of $z$-$w$ path, then from $y_{i-1}$ to $u$ on the first part of
$P_2$, then from $u$ to $v$ on
$P_1$, then from $v$ to $y_i$ on the second part of $P_2$, then from
$y_i$ to $w$ on the second part of the $z$-$w$ path.
\end{proof}

%[[[From here to end of this subsection, we have some old proof
%sketches for the various other implications.]]]

\remove{
1 implies 3
  Suppose we have a connected graph with no cycles.  Consider vertices
  $x$ and $y$.  Have a path, since connected.  Why unique?  Because
  concatenation of two distinct paths (one $x$-$y$, other reversed
  $y$-$x$) form a circuit (slightly tricky to prove; need to rule out
  taking a path and its reversal, which is a circuit but contains no
  cycle).  So first def implies second.
%
Explain minimal: poset, under containment of edges.
%
3 implies 2:
Suppose unique simple path between every pair.  Then connected.
Suppose $(u,v)$ is an edge.  Then it is unique simple path from $u$ to
$v$.  So if remove, $u$ and $v$ are disconnected.
%
2 implies 1
Suppose removing any edge disconnects.  Claim no cycle.  Proof:
suppose $v_1,\ldots,v_k,v_1$ is a cycle.  Then if graph is connected,
can remove edge $(v_1,v_2)$ and stay connected.  Why?  Take vertices
$x$ and $y$.  Connected before, so path between them.  If use edge
$(v_1,v_2)$, can replace with path $v_2,v_3,\ldots,v_k,v_1$ to get new
path.
} % end remove 

% 3:30

\subsection{Counting tree nodes and edges}

\begin{definition}
A \emph{leaf} is a node of degree 1.
\end{definition}

\begin{lemma}
Any tree with more than one vertex has at least one leaf.
\end{lemma}

\begin{proof}
Consider a longest simple path $v_1,\ldots,v_k$ (why does such
exist?). \\
Claim $v_1$ is a leaf. \\
Proof: suppose not.  \\
Then $v_1$ has a second neighbor $x$. \\
Is $x=v_i$ for some $i$?  No, that would give a simple cycle of length
$> 2$.  \\
Thus $x,v_1,\ldots,v_k$ is a longer simple path, a contradiction.
\end{proof}

The following is ``obvious,'' but I'll write down a proof for those who
want to read it.
\begin{lemma}
If we remove a leaf and its edge from a tree, we get a tree.
\end{lemma}

\begin{proof}
  Suppose we remove leaf $v$ and its one incident edge $(u,v)$.  We
  need to show the remaining graph is still connected (it is clearly
  still acyclic).  Consider the unique simple path between two other
  vertices $x$ and $y$.  Can $(u,v)$ be on this path?  No, because
  $(u,v)$ is the only edge incident on $v$, so we would have to
  traverse it twice to enter and leave $v$.  This would make a
  non-simple path.

  Since $(u,v)$ is not on the path from $x$ to $y$, there is still a
  path after we delete $(u,v)$.  This is true for all pairs $x$ and
  $y$, so the remaining graph is connected.
\end{proof}

\begin{lemma}
Any tree on $n$ vertices has $n-1$ edges.
\end{lemma}

\begin{proof}
By induction on $n$, starting from $n=1$. \\
Base case is trivial. \\
Inductive step: \\
Start with an arbitrary tree with $n+1$ nodes.
Remove one node and its incident edge.
By the previous lemma, the result is a tree (with $n$ nodes).
By the inductive hypothesis, this tree has $n-1$ edges.
So the original tree has $n$ edges.
\end{proof}

\begin{lemma}
Any $n$ vertex connected graph $G$ with $n-1$ edges is a tree.
\end{lemma}

\begin{proof}
Let's use the second definition of a tree---minimal connected
graph. \\
We are assuming that $G$ is connected. \\
We must show that if we remove any edge from $G$, the resulting graph
is disconnected. \\
\\
Since $G$ has $n-1$ edges, removing any edge reduces the number of
edges below $n-1$. \\
But we proved earlier that to be connected (have one connected
component) a graph must have at least $n-1$ edges.  \\
So that means that removing any edge disconnects the graph.
\end{proof}

So, we actually have yet another equivalent definition of a tree:
a connected graph with $n$ nodes and $n-1$ edges (for some $n$).

\remove{
[[[The following are some leftover related lemmas.]]]
%
\begin{lemma} Any graph with finitely many vertices and minimum
  degree 2 or more has a cycle. 
\end{lemma}
%
\begin{proof}
  Start at some vertex $v_0$.  It has at least one neighbor $v_1$.
  Now define $v_k$ to be some neighbor of $v_{k-1}$ that is \emph{not}
  $v_{k-2}$.  Always exists by minimum degree 2, so well defined.
  Suppose $n$ vertices.  By pigeonholing, two of $v_0,\ldots,v_n$, say
  $v_i$ and $v_j$, are same vertex.  Then $v_i,\ldots,v_j$ is a
  circuit, can turn to cycle.
\end{proof}
%
Not true for infinite graph.  Counterexample?
%
\begin{corollary}
Any $n$ vertex graph with $n$ (or more) edges has a cycle.
\end{corollary}
%
\begin{proof}
Well ordering.  Let smallest counterexample have $n$ vertices and $m
\ge n$ edges and no cycle.  Suppose has degree 0 node.  Deleting it
reduces $n$ but not $m$, doesn't create a cycle.  Contradicts choice
of $n$.  Suppose has degree 1 node $v$ with incident edge $e$.   Then
deleting $v$ and $e$ gives a graph with $n$ and $m$ reduced by $1$,
contradicts choice of $n$
(technical point: why is this still a graph?  Because we deleted every
edge that uses $v$).  So minimum node degree is 2.  But this must have
cycle by previous lemma.
\end{proof}
} % end remove

% 3:35

\subsection{Spanning Trees and Forests}

This subsection wasn't covered in lecture, but will be covered in
Friday's tutorial.

We've just seen that the ``minimal'' (poset, under edge containment)
connected graphs are trees.  It turns out that every connected graph
contains a tree:
\begin{definition}
A \emph{spanning tree} of a graph is a subset of the graph edges that
forms a tree on all the graph nodes.
\end{definition}
Example \\
\\
Notice that the notion ``tree'' is an intrinsic concept (cares only
about the nodes adjacent to the edges of the tree), while ``spanning
tree'' is extrinsic (cares about whether you have all the graph's
nodes).
\begin{lemma}
Every connected graph contains a spanning tree.
\end{lemma}

\begin{proof}
By contradiction. \\
Suppose there is some counterexample, and use well-ordering to obtain
a counterexample graph $G$ with the fewest edges. \\
Because it's a counterexample, $G$ is connected, but has no spanning tree. \\
\\
There are two cases: \\
\\
1. You can delete some edge from $G$ and stay connected. \\
Then you get a smaller counterexample (still have no spanning tree). \\
That contradicts the way $G$ was chosen. \\
\\
2. Any way of deleting an edge disconnects $G$. \\
But that means that $G$ itself is a tree. (Second definition of tree). \\
So $G$ does have a spanning tree (itself).  Contradiction.
\end{proof}

Example: \\
The notion of a spanning tree arises in computer network graphs. \\
A network graph generally connects nodes by multiple paths, in order
to tolerate failures, changes in the network, and congestion. \\
But during relatively stable, lightly-loaded periods of time, it's
desirable to minimize the amount of communication, and conduct the
communication on predictable paths. \\
For this purpose, a spanning tree of the portion of the network
involved in some application is generally constructed (e.g., IP
Multicast does this) and used for communication. \\
\\
Some graphs aren't connected; they don't have spanning trees.
Instead, they have spanning \emph{forests}:
\begin{definition}
A \emph{forest} is any acyclic graph.
\end{definition}
\begin{lemma}
Each connected component of a forest is a tree.
\end{lemma}

\begin{proof}
Each connected component of a forest is connected and acyclic.
\end{proof}

\begin{definition} 
A \emph{spanning forest} for a graph $G$ is a forest that connects
every pair of vertices that were connected in $G$,
\end{definition}
Example \\
%\\
%People take some liberties with ``tree:'' they call a set of edges a
%tree if it connects its vertices and is acyclic.  So we talk about a
%forest as being ``a collection of trees'' even though each tree is
%only on vertices of a connected component, not on all graph vertices. \\
%\\
Thus, a spanning forest $G$ is just a collection of trees,
one spanning each connected component of $G$.

% 3:45

\subsection{Rooted Trees}

Trees in CS (and elsewhere) are often drawn in a particular
orientation, one node at the top, called the \emph{root}, and the
others on paths moving downward. \\
(Of course, \emph{real} trees, like maples, etc., have the root at the
bottom, but no one in CS seems to have noticed this.) \\
\\
This depends on distinguishing one node, any node, as root. \\
Level $0$ node. \\
Then all its neighbors drawn just below it, level $1$. \\
Then all their neighbors, level $2$, etc. \\
\\
\emph{Rooted tree} = undirected tree + root. \\
Maximum level number $=$ \emph{height} of rooted tree. \\
\\
Sometimes ``orient'' (direct) all the edges downward, producing a
directed tree. \\
Note different roots yield different directed trees (could even have
different heights). \\
\\
Example \\
\\
Terminology: \\
\emph{Parent}, \emph{sibling}, \emph{ancestor}, \emph{descendent}.  
From genealogy. \\
\emph{Subtree}. \\
\\
Note:  Changing the order of siblings doesn't change the tree. \\
\\
Examples of uses of rooted trees: \\
\\
Representing organization structure (who reports to whom). \\
\\
Representing computer file systems (UNIX, almost) \\
Each internal node corresponds to a directory, and each leaf
corresponds to a file.  \\
If one directory contains another, there there is an edge between the 
associated internal nodes. \\
If a directory contains a file, then there is an edge between
the internal node and a leaf. \\
\\
See more later. \\
\\
Some special kinds of rooted trees: $m$-ary, full $m$-ary, complete $m$-ary \\
\\
Definition:  An $m$-ary tree, $m \geq 1$, is a rooted tree in which
every internal vertex has no more than $m$ children. \\
\\
Special case where $m = 2$ is binary tree. \\
Almost the same as we defined earlier in term (as an example to
illustrate recursive definitions and structural induction). \\
Slight difference:  Now we're not distinguishing left and right. \\
(If we want to do this, we should call the structure an
\emph{ordered rooted tree} instead of just a rooted tree.) \\
\\
Definition:  A \emph{full} $m$-ary tree is an $m$-ary tree in which
each internal node has exactly $m$ children. 
(However, all leaves need not be at the same level.) \\
A \emph{complete} $m$-ary tree is a full $m$-ary tree in which all the
leaves are at the same level. \\
\\
Examples 

\subsection{Counting on rooted trees}

What can we say about number of vertices, edges, internal vertices,
leaves, etc., in $m$-ary trees? \\
Fix some values. \\
Suppose that $T$ is a full $m$-ary tree ($m \geq 2$) with $l$ leaves,
$i$ internal nodes, $e$ edges, and $n$ total nodes. \\
Start with the most restrictive case, complete $m$-ary trees:
\begin{theorem}
For a complete $m$-ary tree ($m \geq 2$):
\begin{enumerate}
\item
$l = m^h$.
\item
$i = {m^h - 1 \over m - 1}$
\item
$n = {m^{h+1} - 1 \over {m - 1}}$
\item
$e = {m^{h+1} - 1 \over m - 1} - 1$
\end{enumerate}
\end{theorem}
\begin{proof}
\begin{enumerate}
\item
$l = m^h$ \\
\\
By induction on $h$. \\
Base:  $h = 0$: $1 = m^0$ leaves. \\
Inductive step: Assume for $h$, prove for $h+1$.  \\
Given tree $T$ of height $h+1$, children subtrees have height $h$, so
by inductive hypothesis, each has $m^h$ leaves. \\
Leaves of whole tree are exactly the leaves of the subtrees. \\
So $m \times m^h$, which $= m^{h+1}$, as needed. \\
\item
Again, use induction on $h$.
\item
Again, use induction on $h$.
\item
Use the previous part and the fact that $e = n - 1$. 
\end{enumerate}
\end{proof}

For a full, but not necessarily complete, tree, things are a little
more complicated:
\begin{theorem}
For a full $m$-ary tree ($m \geq 2$):
\begin{enumerate}
\item
($n$ in terms of $i$.)
$n = mi + 1$.
\item
($i$ in terms of $n$.)
$i = {n - 1 \over m}$.
\item
($l$ in terms of $n$)
$l = {(m-1)n + 1 \over m}$.
\item
($n$ in terms of $l$)
$n = {ml - 1 \over m - 1}$.
\item
($l$ in terms of $i$)
$l = (m-1)i + 1$.
\item
($i$ in terms of $l$)
$i = {l - 1 \over m - 1}$.
\end{enumerate}
\end{theorem}

\begin{proof}
\begin{enumerate}
\item
Every vertex except the root is the child of an internal vertex. \\
So $n$ is equal to $1$ plus the number of child vertices. \\
Claim there are exactly $mi$ child vertices, since there are $i$
internal vertices and each has exactly $m$ children. \\
\item
Just solve the previous for $i$.
\item
Combine obvious fact $l = n - i$ and previous part.
\item
Solve previous for $n$.
\item
Combine obvious fact and part 1.
\item
Solve previous for $i$.
\end{enumerate}
\end{proof}

These exact results can be used to get inequalities for arbitrary
$m$-ary trees, for example:
\begin{enumerate}
\item
$l \leq m^h$.
\item
$i \leq {m^h - 1 \over m - 1}$
\item
$n \leq {m^{h+1} - 1 \over m - 1}$
\item
$e \leq {m^{h+1} - 1 \over m - 1} - 1$
\item
$n \leq mi + 1$.
\item
$i \geq {n - 1 \over m}$.
\item
$l \leq {(m-1)n + 1 \over m}$.
\item
$n \geq {ml - 1 \over m - 1}$.
\item
$l \leq (m-1)i + 1$.
\item
$i \geq {l-1 \over m - 1}$.
\end{enumerate}
Proof: LTTR.

\subsection{Applications of Trees}

\subsubsection{Binary Search Trees}

To aid in storing and searching for data. \\
Store data with \emph{keys} from totally ordered set, at nodes of
ordered binary tree. \\
Do this to make it fast to insert and look up items using their keys. \\
Invariant property to maintain: \\
Any value occurring in left subtree of node is $<$ value at node. \\
Any value in right subtree of node is $>$ value at node. \\
\\
Example \\

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/fall00/newlectures/figures/bst.eps,height=2in}}
\caption{A binary search tree}
\label{fig:bst}
\end{figure}

Fast for searching. \\
E.g. to see if $m$ is in tree, compare from top, go left if less, go
right if greater, etc.; trace and reach it. \\
E.g., to see if $n$ is in tree, trace -- not there. \\
The beauty is that the whole tree need not be searched, just one path. \\ 
Usually faster, unless tree is very skewed. \\
\\
Fast also for insertion of new data.  Trace. \\
\\
Deletion may leave empty nodes, needs special reorganization methods. \\
See in 6.046.

\subsubsection{Compiling}

Very important use of trees is to represent programs, and pieces of
programs, internally during the compilation process.  \\
Trees give the structure of the program, which is not made explicit in
a linear text representation. \\
\\
Example: Arithmetic expressions \\
\\
E.g., (2 + x) - (3 - (x + y)) \\
Ordered tree. \\
\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/fall00/newlectures/figures/expr.eps,height=2in}}
\caption{Parse tree for above arithmetic expression}
\label{fig:expr}
\end{figure}

Example: More interesting program structure: \\
\begin{verbatim}
if x > y then while x <= 5 do x := x+1; a:= a^2
\end{verbatim}

This kind of tree is called a \emph{parse tree}.  \\
It is produced during the compilation process, by a compiler program. \\
\\
Besides containing such structural information, it gets decorated with other
information, like the types of the variables. \\
It is then used as the basis for generating machine code. 

\subsubsection{Decision Trees}

Can represent the decision structure of a program. \\
Unwind loops, represent as tree. \\
\\
Example: Sorting a list of $4$ numbers $a,b,c,d$ (assume unequal) \\
\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/fall00/newlectures/figures/decision.eps,height=2.5in}}
\caption{Decision tree for sorting}
\label{fig:decision}
\end{figure}

Answers at bottom. \\
Height of tree corresponds closely to worst-case running time.

\end{document}

\endinput






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
