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

\textwidth=6.5in
%\topmargin=-.15in
%\evensidemargin=0.75in
%\oddsidemargin=0.7pt
%\newcommand {\pindent} {\hspace*{20pt}}
\textheight=9.5in
\parskip=12pt plus 2pt minus 2pt
\pagestyle{empty}
\setlength{\parindent}{0in}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\newcommand{\pagetitle}[1]{\newpage {\bf #1} \hfill
L6$-$P. \thepage \\ \vspace{-0.5cm} \hrule \vspace{12mm}}
\newcommand{\doublespace}{\addtolength{\baselineskip}{.35\baselineskip}}
%\newcommand{\remove}[1]{}

\begin{document}

\renewcommand{\thepage}{\arabic{page}}


\Huge
\pagetitle{Lecture Overview}
Partially ordered sets (continued)\\
\\
Digraphs\\
\\
Graphs \\
\\
Graph Coloring\\
\\
Graph connectivity\\


\pagetitle{Parallel Task Scheduling}

\noindent
Example for partially ordered set

\noindent
Given a finite poset of tasks, how long does it take to do them all?\\
One time unit for a task,\\
Unlimited number of processors.\\
For example in the dressing example we could do all minimal
elements first (left sock, right sock, underwear, shirt),
remove and repeat.

\setlength{\unitlength}{0.027500in}%
%\setlength{\unitlength}{0.012500in}%
                                %
\begingroup\makeatletter\ifx\SetFigFont\undefined
                                % extract first six characters in \fmtname
\def\x#1#2#3#4#5#6#7\relax{\def\x{#1#2#3#4#5#6}}%
\expandafter\x\fmtname xxxxxx\relax \def\y{splain}%
\ifx\x\y   % LaTeX or SliTeX?
\gdef\SetFigFont#1#2#3{%
  \ifnum #1<17\tiny\else \ifnum #1<20\small\else
  \ifnum #1<24\normalsize\else \ifnum #1<29\large\else
  \ifnum #1<34\Large\else \ifnum #1<41\LARGE\else
  \huge\fi\fi\fi\fi\fi\fi
  \csname #3\endcsname}%
\else
\gdef\SetFigFont#1#2#3{\begingroup
  \count@#1\relax \ifnum 25<\count@\count@25\fi
  \def\x{\endgroup\@setsize\SetFigFont{#2pt}}%
  \expandafter\x
  \csname \romannumeral\the\count@ pt\expandafter\endcsname
\csname @\romannumeral\the\count@ pt\endcsname
  \csname #3\endcsname}%
\fi
\fi\endgroup
\begin{picture}(220,75)(20,760)
  \thinlines
  \put(165,817){\vector( 0,-1){ 20}}
  \put(240,817){\vector( 0,-1){ 20}}
  \put(240,787){\vector( 0,-1){ 20}}
  \put(165,787){\vector( 0,-1){ 20}}
  \put( 25,797){\vector( 0,-1){ 25}}
  \put( 85,797){\vector( 0,-1){ 25}}
  \put(180,787){\vector( 3,-1){ 51}}
  \put(178,765){\vector( 1, 0){ 53}}
  \put(153,795){\vector(-4,-1){88}}
  \put(155,790){\makebox(0.1111,0.7778){\SetFigFont{5}{6}{rm}.}}
\put(153,790){\vector(-2,-1){ 32}}
  \put( 20,800){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}left sock}}}
  \put( 20,765){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}left shoe}}}
  \put( 80,800){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}right sock}}}
  \put(235,820){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}shirt}}}
  \put(155,820){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}underwear}}}
  \put(235,790){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}sweater}}}
  \put(235,760){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}jacket}}}
  \put(155,760){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}belt}}}
  \put(155,790){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}pants}}}
  \put( 80,765){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}right shoe}}}
\end{picture}

\noindent
Definition: A {\bf chain\/} in a poset is a sequence of elements of the domain,
  each of which is smaller than the next in the partial order
  ($\preceq$ and $\neq$).

\noindent
A longest chain is also known as a {\em critical path}. \\
Let $t$ be the length of the longest chain.

\pagetitle{Chains of Posets}

Theorem: Given any finite poset $(A, \preceq)$ for which the longest chain
has length $t$, it is possible to partition $A$ into $t$ subsets,
$A_1, A_2, \cdots, A_t$ such that
$(\forall i \in [1,t]) (\forall a \in A_i)
(\forall b \preceq a, b \neq a)
[ b \in A_1 \cup A_2 \cup \cdots \cup A_{i-1} ]$.

\noindent
proof: Put each $a$ in set $A_i$, where $i$ is the length of the
longest chain ending at $a$.\\

\noindent
Need to show $(\forall i) ( \forall a \in A_i)$ \\
$(\forall b \preceq a, b \neq q)
[ b \in A_1 \cup A_2 \cup \cdots \cup A_{i-1} ]$. \\
\\
Proof by contradiction: \\
If $b \not\in A_1 \cup A_2 \cup \cdots \cup A_{i-1}$ then there is a path
of length $>i-1$ ending in $b$, \\
which means there is a path of length $>i$ ending in $a$, \\
which means $a \not \in A_i$. 

\noindent
We can schedule the tasks in $t$ time units.

\pagetitle{Antichains }

\noindent
An {\bf antichain\/} is a set of incomparable elements.

\noindent
(Dilworth) $\forall t$, every poset with $n$ elements must have a
  chain of size $ > t$ or an antichain of size $\geq \frac{n}{t}$.

\setlength{\unitlength}{0.027500in}%
%\setlength{\unitlength}{0.012500in}%
                                %
\begingroup\makeatletter\ifx\SetFigFont\undefined
                                % extract first six characters in \fmtname
\def\x#1#2#3#4#5#6#7\relax{\def\x{#1#2#3#4#5#6}}%
\expandafter\x\fmtname xxxxxx\relax \def\y{splain}%
\ifx\x\y   % LaTeX or SliTeX?
\gdef\SetFigFont#1#2#3{%
  \ifnum #1<17\tiny\else \ifnum #1<20\small\else
  \ifnum #1<24\normalsize\else \ifnum #1<29\large\else
  \ifnum #1<34\Large\else \ifnum #1<41\LARGE\else
  \huge\fi\fi\fi\fi\fi\fi
  \csname #3\endcsname}%
\else
\gdef\SetFigFont#1#2#3{\begingroup
  \count@#1\relax \ifnum 25<\count@\count@25\fi
  \def\x{\endgroup\@setsize\SetFigFont{#2pt}}%
  \expandafter\x
  \csname \romannumeral\the\count@ pt\expandafter\endcsname
\csname @\romannumeral\the\count@ pt\endcsname
  \csname #3\endcsname}%
\fi
\fi\endgroup
\begin{picture}(220,75)(20,760)
  \thinlines
  \put(165,817){\vector( 0,-1){ 20}}
  \put(240,817){\vector( 0,-1){ 20}}
  \put(240,787){\vector( 0,-1){ 20}}
  \put(165,787){\vector( 0,-1){ 20}}
  \put( 25,797){\vector( 0,-1){ 25}}
  \put( 85,797){\vector( 0,-1){ 25}}
  \put(180,787){\vector( 3,-1){ 51}}
  \put(178,765){\vector( 1, 0){ 53}}
  \put(153,795){\vector(-4,-1){88}}
  \put(155,790){\makebox(0.1111,0.7778){\SetFigFont{5}{6}{rm}.}}
\put(153,790){\vector(-2,-1){ 32}}
  \put( 20,800){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}left sock}}}
  \put( 20,765){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}left shoe}}}
  \put( 80,800){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}right sock}}}
  \put(235,820){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}shirt}}}
  \put(155,820){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}underwear}}}
  \put(235,790){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}sweater}}}
  \put(235,760){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}jacket}}}
  \put(155,760){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}belt}}}
  \put(155,790){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}pants}}}
  \put( 80,765){\makebox(0,0)[lb]{\smash{\SetFigFont{12}{14.4}{Huge}right shoe}}}
\end{picture}

$n=10$, $t=3$ there exists a chain of length 4.\\

$t=4$, no chain of length 4, but antichain of size 
$4 \geq \frac{10}{4}$.


\pagetitle{Dilworth }

\noindent
(Dilworth) $\forall t$, every poset with $n$ elements must have a
  chain of size $ > t$ or an antichain of size $\geq \frac{n}{t}$.

\noindent
Proof: Assume there is no chain of length $> t$. \\
  So, longest chain has length $\leq t$. \\
  Then by previous result, the $n$ elements can be partitioned into
  $\leq t$ antichains. \\
  (Cannot assume exactly $t$, since could have some empty.) \\
  So there is an antichain with $\geq \frac{n}{t}$
  elements. \\
  As needed.

Corollary: 
  Every poset with $n$ elements has a chain of length $> \sqrt{n}$
  or an antichain of size $\geq \sqrt{n}$.

Examine $t= \sqrt{n}$ 

\pagetitle{Number of Comparisons for Database\\ Setup and Searching}
Database of records with distinct numerical keys.\\
Suppose an insert requires comparisons.\\
Each comparison costs the time to perform it.\\
One extreme, database kept totally sorted\\
or totally unsorted.\\
A search for a record with key $k$.\\
The worst-case number of comparisons depends on database partial order\\
Database totally sorted, start in the middle ---\\
Binary search\\
Approximately $\log{n}$ comparisons needed. \\
For any $t$, either have a chain of length $> t$, or an antichain of
size $\geq \frac{n}{t}$.  \\
Setting up a chain of length $> t$ requires at least $t$ comparisons. \\
The antichain requires at least $\frac{n}{t}$ comparisons. \\
We have to pay the cost sometime --
tradeoff -- either we do $> t$ comparisons setting up the db,
or at least $\frac{n}{t}$ in the worst case to search the db. 

\pagetitle{Logical Time in Distributed Systems}
A distributed computation:\\
sequence of ``steps'' by each of $n$ processes

local steps, {\it send} steps, {\it receive} steps

Processes are working independently,\\
interaction by messages

dependence among steps:\\
Successive steps of same process\\
Send vs. receive of same message

the reflexive transitive closure is a partial order

Basic theorem:  Any topological sort of this partial order
describes a possible
sequence in which all the distributed steps could occur. \\
(No changes in what happens based on reordering incomparable steps.) 

Lamport --- have a logical time for every step\\
can be used for time-stamping update a shared file


\pagetitle{Directed Graphs --- (Digraphs)}
Digraphs and binary relation are equivalent\\

Edges are arrows\\
(Each edge is an ordered pair)

Precedence Constrains (relations)\\

\begin{figure}[htbp]
\mbox{\includegraphics{/a/class/6.042/spring00/archive/lectures/figures/dividehasse}}
\end{figure}

\pagetitle{Digraphs, Cont. }

A {\it directed graph} $G(V,E)$ is a pair of sets $(V,E)$.\\
$V$ is the set of {\em vertices}\\
$E$ is the set of {\em edges} --- an edge is a pair of 
distinct vertices

Diagram:
\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/digraph.eps,height=2.5in}}
\end{figure}

$V=\{1,2,3,4\}$, $E=\{(1,2),(2,1),(2,4),(4,3)\}$

For a relation $R$ on a finite set $A$,\\
$V = A$, the underlying set, and\\
$E = R$, the relation,\\
the set of ordered pairs $(x,y)$ such that $x R y$.

\pagetitle{Digraphs, Examples}

Tournament digraphs (a directed edge between any two)\\

Computer networks:\\
$~~~~V$ set of Computers,\\
$~~~~E$ Communication links\\
\\
Airline Connections:\\
$~~~~V$ Airports,\\
$~~~~E$ flights\\
\\
Precedence Constraints (e.g., dressing, prerequisites):\\
$~~~~V$ Jobs,\\
$~~~~E$ Constrains on job scheduling\\
\\
Program Flowchart:\\
$~~~~V$ step of computation,\\
$~~~~E$ control flow

\pagetitle{Digraphs, Cont.}

\noindent
Weighted Graphs --- A number is associated with each edge.\\
A {\em weight} $w(u,v)$ for each edge $(u,v)$.\\
E.g., time for airline trip

$x$ is the {\it initial vertex} of an edge $(x,y)$ \\
$y$ is the {\it terminal vertex}

{\it in-degree} of $x$, \# of edges with $x$ as terminal\\
{\it out-degree} of $x$, \# of edges with $x$ as initial\\

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/digraph.eps,height=2.5in}} 
\label{fig:digraphio}
\end{figure}

in-degree of vertex $2$ is 1 out degree of vertex $2$ is 2.

\pagetitle{Paths in Digraphs}
Theorem:
Sum of the indegrees of all nodes in a graph
  = sum of outdegrees of all nodes in the graph
  = number of edges

Proof: induction on the number of edges,\\
Base: a graph with no edges\\
Step: consider a graph with $n+1$ edges and remove an edge

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

A {\em 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.

The {\em length\/} of the path is $k$ (the number of edges).

A path of length $0$, is a single vertex $u_0$.\\
(Rosen's definition: paths have at least one edge).

\pagetitle{Paths in Digraphs, Cont.}

A path may contain the same edge or vertex multiple times.\\

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/digraph.eps,height=2.5in}}
\end{figure}

$u= 1,2,1,2,4,3$ is a path of length 5

A path is {\em simple\/} if no vertex appears more than once,\\
Possible exception the first vertex may be the same as the last\\
(Rosen: defines ``simple'' to mean ``no repeated edges''.)

$1,2,4,3$ and $2,1,2$ are simple paths,\\
while $2,1,2,4$ is not simple.

\pagetitle{Path in a Digraph, Cont.}

Theorem:
If $|V| = n$, then any simple path has length at most $n-1$.

Theorem:  
If $|V| = n$, and a path from $u$ to $v$ exists in $G$,\\
then there is a simple path (of length $n-1$) from $u$ to $v$

Proof:
Consider the shortest path from $u$ to $v$\\
If not a simple path---so some vertex is repeated.\\
The path $u_0,\ldots,u_i,\ldots,u_j,\ldots,u_k$ has $u_i=u_j$.\\
$u_0,\ldots,u_i,u_{j+1},\ldots,u_k$ is a shorter path\\
A contradiction.

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/digraph.eps,height=1.5in}}
\end{figure}

$u= 1,2,1,2,4,3$ can be shorten to $1,2,4,3$

{\em Circuit\/} (also known as a {\em cycle\/})\\
a path that begins and ends at the same vertex.

\pagetitle{Paths and\\ Relational Operations}

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.)

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 {\em connected to\/} $v$ in $G$.)

Adjacency matrix representation can be used to calculate
the needed products and take the needed closures.

\pagetitle{Euler Circuits}

Euler circuit in digraph $G$:
A circuit in $G$ that traverses each edge of $G$ exactly once.

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/digraph.eps,height=2.5in}}
\end{figure}

An Euler circuit exists if we add the edge (3,2).

Digraph $G$ is {\em strongly connected\/} if there is 
a path from every vertex to every other vertex.

Digraph $G$ is {\em weakly connected\/} if there is a path between
any two vertices in the underlying undirected graph

\pagetitle{Euler Circuits, Cont.}
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.

Proof: \\
Only if -- we cannot traverse all edges of a node otherwise,\\
In-degree greater than out-degree then cannot exit,\\
Out-degree greater than in-degree then cannot enter sufficient number
of times

If --- first the existence of a circuit:\\
Start with any edge, and trace nodes,\\
Until arriving to a node with all outgoing edges traced.
(This is the node we started in
since whenever we reach another node,
the number of the in-going edges
that were traversed is one smaller than the number
of out-going edges that we traversed.)

Choose a maximum length circuit $C$ with no repeating edge,\\
If it does not include an edge, then \\
$H$ is subgraph of $G$\\
Consisting all edges in $G$ not in $C$.

There exists a node $u$ in $H$ that is also in $C$.\\
For if not, $G$ is not weakly connected:\\
No edge connects a node in $H$ with a node in $C$.

$u$ has a non traversed (ingoing our outgoing) edge\\
$u$ must have an outgoing edge that was not traversed\\
(the number of traversed ingoing and outgoing edges must be equal).

Starting with that outgoing edge, construct a cycle in $H$,
eventually, it gets back to $u$.

Now we have two cycles with disjoint edge sets and a common vertex,
$u$.\\
Can splice them together to get a larger cycle than $C$.
Contradicts choice of $C$ as maximum.


\pagetitle{Undirected Graphs}

\noindent
\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/graph.eps,height=2.5in}}
\end{figure}

{\em Undirected} graphs correspond to symmetric relations ---
if $(u,v)$ exists then $(v,u)$ exists.

$V=\{1,2,3,4\}$ and $E=\{(1,2),(1,3),(2,3),(3,4)\}$\\ (unordered pairs)

More Terms:\\
Vertex 1 is {\it adjacent} to vertex 2, but not to vertex 4.\\
Edge $(u, v)$ is {\em incident} or {\it attached} to vertices $u$ and $v$.\\
Vertices $u$ and $v$ are {\em adjacent} or {\em neighbors}.\\
``an edge joins $u$ and $v$'', ``the edge between $u$ and $v$''


\pagetitle{More Graphs }

Multigraph ---
Neighbors can be connected by several edges.

Self-Loops --- an edge that connects a vertex to itself.

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/multigraph.eps,height=2.5in}}
\end{figure}

A multigraph with a self-loop.  \\
three edges connecting vertices 1 and 2 and\\
a self-loop on vertex 3.

\pagetitle{Standard Graphs}

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/zoo.eps,height=4.0in}}
\end{figure}

\noindent
(a) The empty graph on five vertices, $E_5$.  An empty
graph has no edges at all.  \\
(b) The cycle (or ring) on five vertices, $C_5$.\\
(c) The complete graph on five vertices, $K_5$. \\
(d) A five-vertex line graph.\\
(e) A $5 \times 5$ 2-dimensional mesh.

\pagetitle{Adjacency Matrices}
The {\em adjacency matrix}

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

Represents:
\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/graph.eps,height=2.5in}}
\end{figure}

\pagetitle{Adjacency Matrices}
What does the following weight-matrix $w(i,j)$ represents?
\[\begin{array}{r|cccc}
& 1&  2&  3& 4\\
\hline 
1& 0&  4&  7&  0\\
2& 4&  0&  1&  0\\
3& 7&  1&  0&  9\\
4& 0&  0&  9&  0\\
\end{array}\]

\noindent
\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/graph.eps,height=2.5in}}
\end{figure}

\pagetitle{Subgraphs, vertex degree}
$G'=(V',E')$ is a {\it subgraph} of $G=(V,E)$ iff
$V' \subseteq V$ and $E' \subseteq E$.

A {\it degree} of a vertex $v$, $d(v)$ is the number of edges
incident to $v$.

What is the degree of a vertex in:\\
Empty graph?\\
Cycle?\\
Complete graph?\\

In a graph with $m$ edges the sum of the degrees is $2m$\\
\\
In every graph there are even number of vertices with odd degree

\pagetitle{Graph Coloring}

Exam scheduling problem.\\
Each vertex represents a course.\\
An edge $(c_1,c_2)$ exists iff there is a student that takes 
both $c_1$ and $c_2$.\\
Each time slot for an exam is represented by a distinct color:
Monday 9-12 by red, Monday 1-4 by blue, etc.\\
No two neighboring vertices
receive the same color.

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/exams.eps,height=3in}}
\end{figure}

$\chi(G)$ the {\it chromatic number} is the minimal number of colors needed
to color $G$ so that no two adjacent vertices receive the same color.

\pagetitle{Graph Coloring, Cont.}
$\chi(G)$ of a triangle graph is $3$.

Upper bounds for a graph with $n$ nodes $\chi(G) \leq n$.

In fact $\Delta+1$, where $\Delta$ is the maximal vertex degree.\\

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/exams.eps,height=4in}}
\end{figure}


\pagetitle{Connectivity}

Connectivity related questions:\\
Is a graph all in one piece or composed of several pieces?\\
What is the length of the shortest path from one vertex to another?\\
Are there many different routes or just one?

A {\em 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\\

A path may contain the same edge or vertex multiple times.

A {\em simple path}, no vertex is crossed more than once.\\
$u_0=u_k$ is permitted.

A {\em circuit} or a {\em cycle} is a path from a vertex back to itself.

\pagetitle{Connected Component}

A graph is {\em connected} if there is a path between every pair of
distinct vertices.

A connected component is a subset of the vertices such that\\
each can reach any other in the subset,\\
but can't reach any vertex not in the subset.\\

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/3comp.eps,height=3.5in}}
\end{figure}

\pagetitle{Connected Component, Cont.}

Connectedness is an equivalence relation ---\\
reflexive --- (if we allow length 0 paths).\\
symmetric --- because we can reverse paths in an undirected graph.\\
transitive --- because we can concatenate paths.\\

Connectedness defines a partition of
the vertices into equivalence classes.\\

Each equivalence class is
called a {\em connected component}.\\

\end{document}
\pagetitle{Cuts}

Empty cuts cause the graph to loss connectivity.

An {\em 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 $V$
and $V-W$ (that is, no edge has one endpoint in each set).

Lemma --- A graph is connected iff it has no empty cuts.

If $G$ has an empty cut then there is no path from $v\in V$ to $w \in V-W$\\
(use well ordering to define the first vertex in the path that is $\not\in V$)

If $G$ is disconnected then there is an empty cut\\
$\exists$ $v,w$ such that there is no path from $v$ to $w$.\\
Let $W$ ($V$) be the set of vertices connected by a path to $w$
($v$, respectively)\\
There is no edge connecting a vertex in 
$W$ to a vertex in $V$.\\
Otherwise, there is a path connecting
$v$ to $w$.

\end{document}
\pagetitle{False Theorem about\\ Connectivity}
If a graph is connected, then every vertex must be connected to some
other vertex.

{\bf False Theorem}
If every vertex in a graph is adjacent to another vertex, then the
graph is connected.

Proof: by induction \\
$P(n)$: an $n$-vertex graph in which every vertex is adjacent to another vertex
is a connected graph.

Base: True for $n=2$ (and $n=1$).\\
Step: Assume for $n$ and prove for $n+1$\\
add a vertex $v$ to any $n$-vertex graph $G_n$\\
must an edge connecting $v$ to a node $u$ in $G_n$\\
Thus, there exists a path from $v$ to any node in $G_n$\\

\pagetitle{False Theorem about\\ Connectivity, Cont.}
However,
\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/3comp.eps,height=3.5in}}
\end{figure}

The error is called ``buildup error'' taking only instance
of size $n$ and extended it by one.\\
There is a possibility
to build an $n+1$-vertex graph from two $n/2$-vertex graphs
and an additional vertex.

A $5$-vertex graph can be built from two $2$-vertex graphs
with additional vertex connected to one of them...

\pagetitle{True Theorem about\\ Connectivity}

{\bf Theorem}
A graph with $k$ edges and $n$ vertices has at least $n - k$ connected
components.

A graph with 100 vertices and 35 edges
must have at least $100 - 35 = 65$ connected components.\\
Intuition, have a clique (full subgraph) to 
use the edges in a small portion of the graph.\\

$P(k)$ --- an $n$-vertex graph with $k$ edges
has at least $n - k$ connected components.  \\
Base case, $P(0)$ --- $n$-vertex graph with 0 edges has 
$n - 0 = n$ components.

Assume that an $n$-vertex graph with $k$ edges
has at least $n-k$ connected components to prove that an $n$-vertex
graph with $k+1$ edges has at least $n-k-1$ connected
components.

\pagetitle{True Theorem about\\ Connectivity Cont.}
Removing an edge $e$ from $n$-vertex $k+1$-edges graph results in
$n$-vertex $k$-edges graph\\
For which there are $n-k$ connected component\\
We can safely continue, did not build a new graph...\\
Now add $e$ back ---\\
Either it connects two vertices in the
same connected component, the number of connected component
is at least $n-k$ as before\\
Or it connects two connected components reducing their number
by one to be at least $n-k-1$.

{\bf Corollary}:
Deleting a graph edge increases the number of components by at most
one.

\pagetitle{Trees}

We proved that\\
A graph with $k$ edges and $n$ vertices has at least $n - k$ connected
components.

So we need $n-1$ edges to have at least $1$ connected component.\\
Is there a connected graph with $n-1$ edges?\\
A line, a Tree

Definition: A tree is a connected graph with no cycles.

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/tree.eps,height=3.0in}}
\end{figure}

This tree has 11 {\it leaves} --- vertices of degree at most one.\\
The remaining 7 vertices are called {\it internal nodes}.

\pagetitle{Trees}

File structure in a computer system ---\\
directory is an internal node\\
leaf is a file\\

Lemma: The following properties of a graph $G$ are equivalent
(each implies the others)

1. $G$ is a connected graph with no cycles\\
2. $G$ is a connected component that is disconnected by the removal
of any edge\\
3. $G$ is a graph with a unique simple path between every pair of vertices

Each of the above defines a tree.

We show $1 \Rightarrow 2$, $2 \Rightarrow 3$, and $3 \Rightarrow 1$.


\pagetitle{Trees, Cont.}
Lemma: $(1\Rightarrow 2)$ A connected graph with no cycles is 
disconnected by the removal of any edge.

Suppose we can delete $(u,v)$ without disconnecting the graph.\\
There must exist a simple path from $u$ to $v$ that does not use $(u,v)$.\\
Adding $(u,v)$ to a simple path that does not use $(u.v)$ creates a cycle.\\
Contradiction the no cycle claim.

\pagetitle{Trees, Cont.}
Lemma: $(2 \Rightarrow 3)$
A connected graph that is disconnected by the removal of any edge has
a unique simple path between any pair of vertices.

Suppose there are two different simple $u-v$ paths\\
$P_1$: $u=x_0,x_1,\ldots,x_k=v$\\
$P_2$: $u=y_0,\ldots,y_l=v$\\
Let $i$ be the smallest such that $x_i\neq y_i$\\
Remove $(y_{i-1},y_i)$ does not disconnect $G$\\
Consider a simple path between $z$ and $w$ \\
Case 1: $(y_{i-1},y_i)$ not on the simple path\\
Case 2: $(y_{i-1},y_i)$ on the simple path ---\\
$P_3$: $z,\ldots,y_{i-1},y_i,\ldots,w$.
First $z$ to $y_{i-1}$ using first part of $P_3$\\
Then $y_{i-1}$ to $u$ using first part of $P_2$\\
Then $u$ to $y_i$ using $P_1$\\
Then $y_i$ to $w$ using second part of $P_3$\\

\pagetitle{Trees, Cont.}
Lemma: $(3 \Rightarrow 1)$
A graph with a unique simple path between any pair of nodes is
connected and has no cycles.

A graph $G$ with a simple path between any pair of nodes
is connected by the definition of connectivity.\\
To see there are no cycles in $G$ 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$:\\
$v_1,\ldots,v_k$ and the edge $(v_1,v_k)$.\\


\pagetitle{Spanning Trees }

Definition: A {\em spanning tree} of a graph is a subset of the graph 
edges that forms a tree on all the graph nodes.

Lemma: Every connected graph contains a spanning tree.

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.

\pagetitle{Spanning Forest }

Graphs that are not connected have a {\it spanning forest}

Definition: A {\it forest} is any acyclic graph.

Definition: A {\it spanning forest} for a graph $G$ is a forest
that connects every pair of vertices that were connected in $G$

A spanning forest of a graph $G$ is a collection of trees,\\
One spanning each connected component of $G$.

\pagetitle{Counting Tree Edges}

A {\it leaf} is a node of degree 1.

Lemma: Any tree with more than one vertex has a leaf.

Consider a longest simple path $v_1,\ldots,v_k$.\\
$v_1$ is a leaf.\\  
suppose not.\\  
Then $v_1$ has a second neighbor $x$. \\ 
$\forall i$ $x\neq v_i$ otherwise we have a cycle.\\
Thus $x,v_1,\ldots,v_k$ is a longer simple path,\\
a contradiction.

\pagetitle{Counting Tree Edges}
Lemma: Any tree on $n$ vertices has $n-1$ edges.

Base $n=1$\\
Inductive step:
Start with an arbitrary tree with $n+1$ nodes.\\
Remove one node and its incident edge.\\
The result is a tree (with $n$ nodes).\\
By the induction hypothesis, this tree has $n-1$ edges.\\
So the original tree has $n$ edges.


Lemma: Any $n$ vertex connected graph $G$ with $n-1$ edges is a tree.

To have one connected component a graph must have at least $n-1$ edges.\\
So if we remove any edge from $G$, it becomes disconnected.

The above is one more definition of a tree.

\pagetitle{Euler Tour}

The Koenigsberg bridge problem:

Can we cross every bridge exactly once, without
repeats, returning to our starting point?

We call such tours ``Euler Tours.''

Theorem: If undirected $G$ has Euler tour, then $G$ is connected and every
vertex has even degree.

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.

\pagetitle{Euler Tour --- Hierholze}
Theorem: If $G$ is connected and has even degree
for every vertex, then it has an Euler tour.

Lemma: If $G$ has even degree for every vertex and at least one edge,
then it has a circuit.

Start in a vertex $u$ with degree at least 2 (there must
exists such vertex)\\
move to a neighbor $v$,
since $v$ has an even degree\\
you may continue to a neighbor $w$...\\
The graph is finite --- you reach a visited vertex.

Proof of theorem:
Assume the longest cycle $C$\\
(obtained by removing segments from a circuit)\\
is not an Euler tour.

Delete $C$ from the graph,\\
Consider a remaining vertex $v$,\\
$G$ is connected thus $v$ has a path to $u$ on $C$\\
$u$ has a circuit on the remaining graph\\
Which contradicts the fact that $C$ is longest

\pagetitle{Hamiltonian Paths}
A slightly different question:\\
is there a tour that traverses every
{\em vertex} exactly once?\\

Such a cycle is called a {\em Hamiltonian Cycle.}\\

In a small variant,\\
a simple path that traverses every vertex exactly
once is a {\em Hamiltonian Path}.\\

Small change, but suddenly, instead of answer being trivial, becomes
very complicated.\\

It is believed that no computer program can answer
this question efficiently (it is NP-complete).

\end{document} 

