\documentstyle[12pt,eclepsf]{article}

\textheight 260mm
\topmargin -10mm
\textwidth 180mm
\oddsidemargin -7mm

\pagestyle{myheadings}
\markright{(Introduction to Graph Theory)}

\begin{document}
\begin{LARGE}


%% ========== title ==========

\vspace*{.6in}
\begin{center}
\begin{Huge}
\noindent
{\bf Introduction to Graph Theory}\\
\end{Huge}

\vspace{1in}
Dokuz Eyl\"{u}l University \\
Engineering Faculty \\
Computer Engineering Department \\ 
14 March -- 26 May, 2000\\
\end{center}


%% ========== Contents ==========
\clearpage
\noindent
$\Box$ {\bf Contents:}\\

\begin{itemize}
\item [ 1.] Basic Principles
\item [ 2.] Graph Theory for Networking.

\end{itemize}




%% ========== what is software engineering? ==========
\clearpage
\noindent
$\Box$ {\bf Basic Principles}\\

\noindent
{\bf Definitions:}
\begin{itemize}
\item vertex ({\it pl. vertices}) \& edge
\item[] (node \& arc)
\item[]
\item multiple edges \& loop
\item simple graph
\item[]
\item connected/disconnected graph
\item[]
\item subgraph
\item[]
\item degree of a vertex
\item regular graph
   \begin{itemize}
   \item all vertices have a same degree
   \end{itemize}
\item[]
\item isomorphic
\item[]
\item labeled/unlabeled

\end{itemize}


%% ========== what is software engineering? ==========
\clearpage
\noindent
$\Box$ {\bf Basic Principles} \hfill cont'd\\

\noindent
$\bullet$ Handshaking Lemma:
\begin{displaymath}
\sum_{i=1}^{N} (\mbox{deg} Q_i) = 2N.\\
\end{displaymath}

\hspace*{1in}\\

\noindent
$\bullet$ Corollary 1:
\begin{itemize}
\item[]The sum of degree of all vertices is always even. \\
\end{itemize}

\noindent
$\bullet$ Corollary 2:
\begin{itemize}
\item[]The number of edges with odd degree is even. \\
\end{itemize}

\noindent
$\bullet$ Corollary 3:
\begin{itemize}
\item[] The number of arcs in a regular graph 
        whose degree is $r$ and number of 
        vertices is $n$\\
        \hspace*{1in}$\Downarrow$ is \\
        \hspace*{.8in}$nr/2$
\end{itemize}


%% ========== what is software engineering? ==========
\clearpage
\noindent
$\Box$ {\bf Basic Principles} \hfill cont'd\\

\noindent
$\bullet$ number of non-isomorphic simple graphs\\

\noindent
{\bf - unlabeled}\\
\begin{table}[hbtp]
\begin{center}
\begin{tabular}{l c c c c c} 
number of vertices & 1 & 2 & 3 &  4 & $\cdots$ \\ \hline
number of graphs   & 1 & 2 & 8 & 64 & $\cdots$
\end{tabular} 
\end{center}
\end{table}

\begin{itemize}
\item[*] The number of all the possible arcs is $n(n-1)/2$ \\
         $\Rightarrow$ exist or not $\Rightarrow 
         2^{n(n-1)/2}$\\
\end{itemize}

\hspace*{1in}\\

\noindent
{\bf - labeled}\\
\begin{table}[hbtp]
\begin{center}
\begin{tabular}{l c c c c c c} 
number of vertices       & 
1 & 2 & 3 &  4 &  5 & $\cdots$ \\ \hline
number of graphs         & 
1 & 2 & 4 & 11 & 34 & $\cdots$ \\
number of connected ones &
1 & 1 & 2 &  6 & 21 & $\cdots$ \\
number of regular ones   &
1 & 2 & 2 &  4 &  3 & $\cdots$ 
\end{tabular} 
\end{center}
\end{table}

\begin{itemize}
\item[*] No such formula exist.
\end{itemize}


%% ========== what is software engineering? ==========
\clearpage
\noindent
$\Box$ {\bf Euler \& Hamilton Graph}\\

\begin{itemize}
\item Definitions:
   \begin{itemize}
   \item walk of length $k$
   \item walk between P and Q
   \item[]
   \item trail
      \begin{itemize}
      \item a walk made up of different arcs
            (but may include the identical nodes.)
      \end{itemize}
   \item path
      \begin{itemize}
      \item A walk made up of different arcs and 
            different nodes.
      \end{itemize}
   \item[]
   \item closed walk
   \item closed trail
   \item closed path $\Rightarrow$ called ``cycle''
   \end{itemize}
\end{itemize}


%% ========== figure  ==========
\clearpage
\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=trail-and-path.eps,width=16cm,height=20cm}
 \end{center}
\end{figure}

%% ========== what is software engineering? ==========
\clearpage
\noindent
$\Box$ {\bf Hamilton and Euler Graph}\\

\begin{itemize}
\item {\bf Travelers Problem}
   \begin{itemize}
   \item Travelers are interested in visiting cities
         as many as possible.
   \item They must visit every city once and only once 
         but may pass some arcs.
   \end{itemize}
\item[] So the problem is to search for 
   \begin{itemize}
   \item {\it cycle(s) that includes all nodes in the graph.}
   \item[] \hspace*{1in} $\Downarrow$ 
           if such cycle(s) exists, it is called
   \item[] {\bf Hamilton Graph} or {\bf Hamiltonian},\\
           and the cycle is called Hamilton cycle.
   \end{itemize}
\item[]
\item Explorers Problem
   \begin{itemize}
   \item Explorers are interested in trails instead.
   \item They may visit same city multiple time
         but only once for one arc.
   \end{itemize}
\item[] So the problem is to search for 
   \begin{itemize}
   \item {\it closed trail(s) that includes all 
              arcs in the graph.}
   \item[] \hspace*{1in} $\Downarrow$ 
           if such trail(s) exists, it is called
   \item[] {\bf Euler Graph} or {\bf Eulerian}.
   \end{itemize}
\end{itemize}

%% ========== figure  ==========
\clearpage
\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=eulerian.eps,width=16cm,height=20cm}
 \end{center}
\end{figure}


%% ========== what is software engineering? ==========
\clearpage
\noindent
$\Box$ {\bf Theorem:}\\

\begin{itemize}
\item Connected graph $G$ is Eulerian iff (if and only if)
      every node has an even order.
\end{itemize}

\hspace*{1in}\\
\hspace*{1in}\\

\noindent
Note:\\
There's no such theorem for Hamiltonian.


%% ========== what is software engineering? ==========
\clearpage
\noindent
$\Box$ {\bf Exercise:}\\

\begin{itemize}
\item Which graphs of the follows \\
      are Hamiltonian and which one are Eulerian? 
\end{itemize}

%% ========== figure  ==========
\clearpage
\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=euler-or-hamil.eps,width=16cm,height=12cm}
 \end{center}
\end{figure}


%% ========== what is software engineering? ==========
\clearpage
\noindent
$\Box$ {\bf Chinese Postman Problem:}\\

\noindent
Since this was proposed by a Chinese mathematician 
named Meign Guan (1962), this is called Chinese $\cdots$.
not a problem regarding \a chinese postman''\\

\begin{itemize}
\item A postman starts his post office to deliver letters
      passing every street, and return to the office 
      with the total distance being minimum.
\end{itemize}

\hspace*{1in}\\
\hspace*{1in}\\
\hspace*{1in}\\

\noindent
$\Box$ {\bf Traveler's Salesman Problem (TSP):}\\

\begin{itemize}
\item A traveler's salesman starts a city 
      visiting every city once and only once 
      with the total distance being minimum.
\end{itemize}

\hspace*{1in}\\
\hspace*{1in}\\
\hspace*{1in}\\

\noindent
{\bf $\Box$ The Shortest Path Problem:}\\

\hspace*{1in}\\
\hspace*{1in}\\

\noindent
{\bf $\Box$ The Longest Path Problem:}\\


%% ========== figure  ==========
\clearpage
\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=postman.eps,width=16cm,height=14cm}
 \end{center}
\end{figure}


%% ========== figure ==========
\clearpage
\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=tsp.eps,width=16cm,height=14cm}
 \end{center}
\end{figure}

%% ========== what is software engineering? ==========
\clearpage

\noindent
$\Box$ {\bf The Shortest Path Algorithm.}\\

\noindent
Notation:\\
$S$: the node to start with, $T$: The goal;\\
$E(U)$: energy of node $U$ 
(the shortest distance from $S$)\\
$e(U)$: energy of node $U$\\
$-------------------------$ \\
\noindent
Step 1
   \begin{itemize}
   \item Assign energy zero to S: $E(S)=0$.
   \item Assign label $\infty$ to all nodes 
                    other than S: $e(S)= \infty$.
   \end{itemize}
\noindent
Step 2
   \begin{itemize}
   \item FOR each of the nodes $U_i$
                    that was already assigned an energy
      \begin{itemize}
      \item FOR each $V_j$ that are directly 
            reachable from $U_i$
         \begin{itemize}
            \item IF $E(U_i)+r(U_i,V_j)<e(W_j)$\\
                  THEN $e(V_j) = E(U_i)+r(U_i,V_j)$
         \end{itemize}   
      \item Find a minimum value of labels 
            among nodes that were not assigned an energy yet,
            and assign energy of that value to the point(s).
      \end{itemize}
   \end{itemize}
\noindent
Step 3
   \begin{itemize}
   \item Repeat step 2 until all nodes are assigned 
                    an energy.
   \end{itemize}
\noindent
Step 4
   \begin{itemize}
   \item Pick up arcs when $E(A)-E(B) = r(A,B)$
   \end{itemize}


%% ========== figure ==========
\clearpage
\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=shortest.eps,width=16cm,height=20cm}
 \end{center}
\end{figure}

%========== Chapter ==========
\clearpage
\begin{Huge}
\hspace*{1in}\\
\hspace*{1in}\\
\hspace*{1in}\\
\noindent
Chapter 2 \\
\hspace*{1in}\\
\hspace*{1in}Graph Theory for Networking.
\end{Huge}


%% ========== what is software engineering? ==========
\clearpage

\noindent
$\Box$ {\bf Network Flow Problem}\\

\begin{itemize}
\item Traveler Problem
\item Explorer Problem
   \begin{itemize}
   \item[$\Rightarrow$] arcs have nothing to do with values.
   \end{itemize}
\item[]
\item (Chinese) Postman Problem
\item Traveler's Salesman Problem
\item The Shortest Path Algorithm
\item The Longest Path Algorithm
   \begin{itemize}
   \item[$\Rightarrow$] each arcs is assigned 
           a value corresponding to {\bf distance}.
   \end{itemize}
\item[]
\item Network Flow Problem
   \begin{itemize}
   \item[$\Rightarrow$] each arc has
           a value corresponding to {\bf capacity}.
   \end{itemize}
\end{itemize}


%% ========== what is software engineering? ==========
\clearpage

\noindent
$\Box$ {\bf Definitions:}\\

\begin{itemize}
\item Bipartite graph:
   \begin{itemize}
   \item If every node belongs to either $A$ or $B$. 
   \end{itemize}
\item[]
\item Complete bipartite graph:
   \begin{itemize}
   \item If every node that belongs to $A$
         is connected all nodes belongs to $B$
         with one and only one arc.
   \end{itemize}
\item[]
\item Complete matching:
   \begin{itemize}
   \item If {\it one-to-one-mapping} from $A$ to $B$ exists.
   \end{itemize}
\end{itemize}


%% ========== what is software engineering? ==========
\clearpage
\begin{center} 
$\Box$ {\bf What condition is needed \\
            for complete matching to exist?}\\

\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\

------ {\bf Marriage Problem} ------ \\
\hspace*{1in}\\
Each boy is a friend of some girls.\\
What condition is needed \\
for every boy to be able to get married \\
with his girl friend? 

\hspace*{1in}\\
$\Downarrow$ e.g.,\\
\hspace*{1in}\\

$b_1$ knows $g_1$, $g_4$ and $g_5$\\
$b_2$ knows $g_1$\\
$b_3$ knows $g_2$, $g_3$ and $g_4$\\
$b_4$ knows $g_2$, $g_4$

\end{center}


%% ========== what is software engineering? ==========
\clearpage
\noindent
$\Box$ {\bf Theorem of Marriage (P.Hall 1935)}\\

\noindent
The condition for the Marriage Problem to exist is \\
that $k$ boys have a total of more than $k$ girl friends\\
for any $k$ that is $1 \le k \le m$, 
where $m$ is the number \\ of boys.\\

\noindent
$\bullet$ Example 2:\\

\noindent
When
\begin{itemize}
\item[-] $a$ knows $w$, $y$ and $z$
\item[-] $b$ knows $x$ and $z$
\item[-] $c$ knows $x$ and $y$
\end{itemize}
\noindent
answer the following questions.\\
\begin{itemize}
\item[(1)] Draw the bipartite graph.
\item[(2)] Find solutions as much as possible, say 5.
\item[(3)] Apply the Marriage Theorem.
\end{itemize}

%% ========== what is software engineering? ==========
\clearpage

\hspace*{1in}\\
\hspace*{1in}\\

\begin{itemize}
\item Example 3:
   \begin{itemize}
   \item A university looks for 4 professors of Mathematics
         Physics, Software Engineering, and Graph Theory.
         There are 5 candidates who can teach
      \begin{itemize}
      \item the 1st $\Rightarrow$ Math.
      \item the 2nd $\Rightarrow$ Phys.
      \item the 3rd $\Rightarrow$ Software Eng.
      \item the 2nd $\Rightarrow$ Graph Th.
      \end{itemize}
   \item[]Then, answer the following questions.
      \begin{itemize}
      \item[](1) Draw the bipartite graph.
      \item[](2) Find solutions.
      \item[](3) Apply the Marriage Theorem.
      \end{itemize}
   \end{itemize}
\item[]
\item Example 4:
   \begin{itemize}
   \item How about the follows?
      \begin{itemize}
      \item $a$ knows $y$ and $u$
      \item $b$ knows $x$, $z$ and $v$
      \item $c$ knows $y$ and $u$
      \item $d$ knows $y$ and $u$
      \end{itemize}
   \end{itemize}
\end{itemize}


%% ========== what is software engineering? ==========
\clearpage
\noindent
$\Box$ {\bf Transversal}\\

The sets of girls known by the four boys:

\begin{displaymath}
\{ g_1, g_4, g_5\}, \{ g_1\}, \{ g_2, g_3, g_4\}, \{ g_2, g_4\}  \\
\end{displaymath}

\hspace*{1in}$\Downarrow$ solution is to find \\

four distinct $g_i$, one from each of these sets of girls.\\

\hspace*{1in}$\Downarrow$ In general,\\

\noindent
If E is a non-empty finite set, and if $\xi = (S_1, S_2, \cdots, S_m)$ 
is a family of non-empty subsets of $E$ (not necessarily distinct.)
Then, a transversal of $\xi$ is a set of $m$ distinct elements of $E$,
one chosen from each set $S_i$.


%% ========== what is software engineering? ==========
\clearpage
\noindent
$\Box$ {\bf Example}\\

\noindent
$
E=\{1,2,3,4,5,6\}\\
S_1=S_2=\{1,2\}, S_3=S_4=\{2,3\}, S_5=\{1,4,5,6\}\\
$



%% ========== what is software engineering? ==========
\clearpage
\noindent
$\Box$ {\bf Theorem:}\\

\begin{itemize}
\item Let E be a non-empty finite set, 
and let $\xi = (S_1, S_2, \cdots, S_m)$ be 
a family of nin-empty subsets of $E$.
Then $\xi$ has a transversal if and only if the union of any $k$ of the 
subsets $S_i$ contains at least $k$ elements $(1\le k \le m)$
\end{itemize}

%% ========== what is software engineering? ==========
\clearpage
\noindent
$\Box$ {\bf Partial Transversal}\\

\noindent
In the previous example:\\

\noindent
$E=\{1,2,3,4,5,6\}\\
S_1=S_2=\{1,2\}, S_3=S_4=\{2,3\}, S_5=\{1,4,5,6\}\\$

\noindent
$\xi$ has no transversal.\\

\hspace*{1in}$\Downarrow$ However\\

\noindent
Subfamily $(S_1, S_2, S_3, S_5)$ has a transversal, e.g.,
\{1, 2, 3, 4\}.\\

\hspace*{1in}$\Downarrow$ A transversal of a subfamily of $\xi$ 
is calld a \\

\noindent
{\bf partial transversal} of $\xi$ \\

\hspace*{1in}$\Downarrow$ Theorem\\

\begin{itemize}
\item $\xi$ has a partial transversal of size $t$ 
iff the union of any $k$ of the subsets $S_i$ contains at least 
$k+t-m$ elements.\\
\end{itemize}

\hspace*{1in}$\Downarrow$ \\

\noindent
A condition under which at least $t$ boys can marry girls known to them.


%% ========== what is software engineering? ==========
\clearpage
\noindent
$\Box$ {\bf Toward Menger's Theorem:}\\

\begin{itemize}
\item definitions
   \begin{itemize}
   \item[*] {\bf edge-disjoint path}
      \begin{itemize}
      \item[] paths between two nodes no two of which have an edge in common.
      \end{itemize}
   \item[]
   \item[*] {\bf vertex-disjoint path}
      \begin{itemize}
      \item[] no two of which have an vertex in common.
      \end{itemize}
   \end{itemize}
\item[]
\item What is the maximum number of these paths?
\end{itemize} 


%% ========== figure  ==========
\clearpage
\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=menger.eps,width=16cm,height=12cm}
 \end{center}
\end{figure}

%% ========== what is software engineering? ==========
\clearpage
\begin{itemize}
\item definitions 2
   \begin{itemize}
   \item[*] {\bf $vw$-disconnecting set of $G$}
      \begin{itemize}
      \item[] a set $E$ of edges of $G$ such that each path from $v$ to 
              $w$ includes an edge of $E$
      \end{itemize}
   \item[]
   \item[*] {\bf $vw$-separating set of $G$}
      \begin{itemize}
      \item[] a set of $S$ of vertices (other than $v$ and $w$)
              such that each path from $v$ to $w$ passes through 
              a vertex of $S$
      \end{itemize}
   \end{itemize}
\end{itemize} 

%% ========== what is software engineering? ==========
\clearpage
\noindent
$\Box$ {\bf Two versions of Menger's Theorem:}\\

\begin{itemize}
\item Edge form:
   \begin{itemize}
   \item[*] The maximum number of edge-disjoint paths connecting 
            two distinct vertices $v$ and $w$ of a connected graph 
            is equal to the minimum number of edges 
            in a $vw$-disconnecting set.
  \end{itemize}
\item[]
\item Vertex form:
   \begin{itemize}
   \item[*] The maximum number of vertex-disjoint paths connecting 
            two distinct vertices $v$ and $w$ of a connected two 
            distinct non-adjacent vertices $v$ and $w$ of a graph
            is equal to the minimum number of vertices
            in a $vw$-separating set.
  \end{itemize}
\end{itemize}

%% ========== what is software engineering? ==========
\clearpage
\begin{itemize}
\item definitions 3
   \begin{itemize}
   \item[*] {\bf $k$-edge-connected}
      \begin{itemize}
      \item[] If the minimum number of edges that we need to delete 
              in order to disconnect $G \ge k$, $G$ is calld 
              $k$-edge-connected
      \end{itemize}
   \end{itemize}
\item[]
\item Corollary 1
   \begin{itemize}
   \item[*] A graph $G$ is $k$-edge-connected iff any two distinct vertices 
            of $G$ are connected by at least $k$ edge-disjoint pahts.
   \end{itemize}
\item[]
\item Corollary 2
   \begin{itemize}
   \item[*] A graph $G$ with at least $k+1$ vertoces is 
            $k$-edge-connected iff any two distinct vertices 
            of $G$ are connected by at least $k$ vertices-disjoint pahts.
   \end{itemize}
\end{itemize} 



%% ========== figure  ==========
\clearpage
\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=cor-1.eps,width=16cm,height=24cm}
 \end{center}
\end{figure}


%% ========== figure  ==========
\clearpage
\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=cor-2.eps,width=16cm,height=24cm}
 \end{center}
\end{figure}



%% ========== what is software engineering? ==========
\clearpage
\begin{itemize}
\item Theorem
   \begin{itemize}
   \item[*] The maximum number of arc-disjoint path from a vertex $v$
            to a vertex $w$ in a directed graph is equal to 
            the minimum number of arcs in a $vw$-desconnecting set.
   \end{itemize}
\item[]
\item Theorem
   \begin{itemize}
   \item[*] Menger's theorem implies Hall's theorem.
   \end{itemize}
\end{itemize} 

\hspace*{1in}\\

\begin{itemize}
\item[] \hspace*{1in}$\Downarrow$ Hints for proof:\\
   \begin{itemize}
   \item[] \hspace*{.1in} Hall's Theorem $\Rightarrow$ bipartite graph
   \item[] while 
   \item[] \hspace*{.1in} Menger's Theorem $\Rightarrow$ general graph\\
   \end{itemize}
\item[] \hspace*{1in}$\Downarrow$ so \\
   \begin{itemize}
   \item[] 1. Add two nodes $v$, $w$ to the bipartite graph.
   \item[] 2. Think what does it mean by {\it edge disjoint path.}
   \end{itemize}
\end{itemize}

%% ========== figure  ==========
\clearpage
\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=dir-menger.eps,width=16cm,height=24cm}
 \end{center}
\end{figure}

%% ========== what is software engineering? ==========
\clearpage
\noindent
$\Box$ {\bf Network Flows:}\\

\noindent
{\bf Definitions:}
\begin{itemize}
\item network
   \begin{itemize}
   \item a directed graph to each arc of which is assigned 
         a non-negative real number $\Pi(a)$, called its capacity.
   \end{itemize}
\item out-degree
   \begin{itemize}
   \item out-degree($x$) of a node $x$ is 
         the sum of the arcs of the form $xz$, i.e.,
      \begin{itemize}
      \item $\mbox{out-degree}(x) = \sum_zxz$
      \end{itemize}
   \end{itemize}
\item in-degree
   \begin{itemize}
   \item similarly,
      \begin{itemize}
      \item $\mbox{in-degree}(x) = \sum_zzx$
      \end{itemize}
   \end{itemize}
\item flow
   \begin{itemize}
   \item a flow in a network is a function $\pi$ that assigns to each arc 
         $p$  a non-negative real number $\pi(p)$ in such a way that\\
         (1) for each arc $p$
            \begin{itemize}
            \item $\pi(p) \le \Pi(p)$
            \end{itemize}
         (2) in-degree and out-degree of each node (except for
             $v$ and $w$) are equal
   \end{itemize}
\item cut
   \begin{itemize}
   \item a set $A$ of arcs such that each path from $v$ to $w$ 
         includes an arc in $A$
   \end{itemize}
\end{itemize}

%% ========== what is software engineering? ==========
\clearpage
\noindent
$\Box$ {\bf Network Flows:} \hfill cont'd\\

\noindent
{\bf Definitions:}
\begin{itemize}
\item zero flow
   \begin{itemize}
   \item the flow in which every arc is zero
   \end{itemize}
\item saturated
   \begin{itemize}
   \item an arc $a$ for which $\pi(a) = \Pi (a)$ is called saturaed
   \end{itemize}
\item maximum flows
   \begin{itemize}
   \item flows whose value is as large as possible
      \begin{itemize}
      \item although a network can have several different maximum flows, 
            their values must be equal.
      \end{itemize}  
   \end{itemize}
\item minimum cut
   \begin{itemize}
   \item a cut in a network is a $vw$-disconnecting set 
         in the corresponding directed graph
   \item the sum of the capacities of the arcs in the cut is 
         called capacity of a cut
   \item those cuts whose capacity is as small as possible
   \item[] \hspace*{.5in}$\Downarrow$ called
   \item minimum cuts
   \end{itemize}
\end{itemize}   


%% ========== figure  ==========
\clearpage
\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=net-flow.eps,width=16cm,height=24cm}
 \end{center}
\end{figure}


%% ====================
\clearpage
\noindent
$\Box$ {\bf An Algorithm for the Muximum Flows:}\\

\noindent
1. Choose a path, regardless of direction of arcs,
\begin{displaymath}
\sum_{i=v}^{w} (e_{ij})
\end{displaymath}

where each $e_{ij}$ has a value $f_{ij}$.\\

\begin{center}
----------------------------------------------
\end{center}

\noindent
This flow is called {\it flow-augmenting} iff
\begin{itemize}
\item when $e_{ij}$ is a same direction as the arc
   \begin{itemize}
   \item[$\star$] $f_{ij}<c_{ij}$ \hspace{.6in} $\Rightarrow$ \hspace{.6in} 
                      $\epsilon_{ij}=c_{ij}-f_{ij}$
   \end{itemize}       
\item when opposite direction
   \begin{itemize}
   \item[$\star$] $f_{ij}>0$  \hspace{.6in} $\Rightarrow$ \hspace{.6in} 
                      $\epsilon_{ij}=f_{ij}$\\
   \end{itemize}
\end{itemize}       


----------------------------------------------\\

\noindent
2. Obtain 
\begin{displaymath} 
\epsilon_{\mbox{min}} = \min\{\epsilon_{ij}\} 
\end{displaymath}


----------------------------------------------\\

\noindent
3. renew $f_{ij}$ as:
\begin{itemize}
\item when $e_{ij}$ is a same direction as the arc
   \begin{itemize}
   \item[$\star$] $f_{ij} = f_{ij} + \epsilon_{\mbox{min}}$
   \end{itemize}       
\item when opposite direction
   \begin{itemize}
   \item[$\star$] $f_{ij} = f_{ij} - \epsilon_{\mbox{min}}$
   \end{itemize}
\end{itemize}       



%% ========== figure  ==========
\clearpage
\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=max-flow-alg.eps,width=16cm,height=26cm}
 \end{center}
\end{figure}


%% ========== figure  ==========
\clearpage
\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=input.eps,width=16cm,height=26cm}
 \end{center}
\end{figure}

%% ====================
\clearpage
\noindent
$\Box$ {\bf Homework:}\\
\begin{itemize}
\item Create a program in C to find a max-flow of {\bf any}
      network whose number of nodes and arcs are not exceeding 40.
\item Input, which is given as a set of connection and capacities, 
      should be fed by ``{\it redirection}''.
   \begin{itemize} 
   \item Note that I will check the code under LINUX 
         with using some of my test cases.
   \end{itemize}
\item Output should be a max-flow.
\item E-mail to akira@cs.deu.edu.tr with attaching two files:
   \begin{itemize}
   \item source code (in ASCII text)
   \item description in POST-SCRIPT
   \end{itemize}
\item[] by the due-date of May 26 (Friday)
\end{itemize}

%% ====================
\clearpage
\noindent
$\Box$ {\bf Toward a Concept of Network Reliability:}\\

\noindent
{\bf Definitions:}
\begin{itemize}
\item Complete graph $\Rightarrow$ $K_{n}$
   \begin{itemize}
   \item When all possible two distinct nodes are connected with each other.
   \item Complete graph with $n$ nodes is denoted as $K_n$
   \item $K_n$ has $\{n(n-1)/2\}$ arcs.
   \end{itemize}
\item Bipartite graph $\Rightarrow$ $K_{n,m}$
\item Edges/Vertices deletion $\Rightarrow$ $G-e/G-v$
\item Contraction $\Rightarrow$ $G/e$
   \begin{itemize}
   \item Remove an edge and identify its both ends.
   \end{itemize}
\item Plane graph
   \begin{itemize}
   \item A graph whose arcs never cross.
   \end{itemize}
\item Planar graph
   \begin{itemize}
   \item A graph isomorphic to a plane graph.\\
   \end{itemize}
\end{itemize}

\hspace*{1in}\\

\noindent
{\bf Note:}\\

\noindent
In the 3-D space, every graph can be drawn in such a way.


%% ========== figure  ==========
\clearpage
\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=deletion.eps,width=16cm,height=26cm}
 \end{center}
\end{figure}


%% ====================
\clearpage
\noindent
{\bf Theorems:}\\

\begin{itemize}
\item $K_{3,3}$ and $K_5$ are not planar.\\
\item A graph is planar iff it cantains no subgraph isomorphic to  
      $K_{3,3}$ and $K_5$ (Kuratowski).\\
\item A graph is planar iff it contains no subgraph contractible to 
      $K_{3,3}$ and $K_5$. 
\end{itemize}


%% ====================
\clearpage
\noindent
{\bf Connectivity revisit:}\\

\begin{itemize}
\item Vertex connectivity $\Rightarrow$ $\kappa(G)$
\item[] (for $\forall k < \kappa(G):$ $G$ is $k$-vertex connected)
   \begin{itemize}
   \item communication is guaranteed even if terminals less than 
         $\kappa(G)$ are out-of-order.
   \item The more the arcs, the more reliable the connectivity
   \item[] \hspace*{1in} $\Downarrow$ But from financial reason, we want
   \item[] a network as reliable as possible\\
         \hspace{2.5in} with arcs as few as possible.
   \end{itemize}
\item Edge connectivity $\Rightarrow$ $\lambda(G)$
   \begin{itemize}
   \item same as above
   \end{itemize}
\end{itemize}


%% ========== figure  ==========
\clearpage
\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=which-is-large.eps,width=16cm,height=26cm}
 \end{center}
\end{figure}


%% ====================
\clearpage
\noindent
{\bf Which Connectivity is larger?}\\
(Compare also with minimum degree $\delta(G)$ and average degree 
   $a(G)=\mbox{\{total-degree\}}/\mbox{\{number of nodes\}} = 2m/n $).\\

\noindent
$\bullet$ Theorem
\begin{displaymath}
\kappa(G) \le \lambda(G) \le \delta(G) \le a(G).
\end{displaymath}


%% ====================
\clearpage
\noindent
{\bf Edge-connectivity of plane graph}\\

\noindent
$\bullet$ Euler's Formula
\begin{displaymath}
n - m + f = 2.\\
\end{displaymath}


\noindent
$\bullet$ Graph may include loop, multiple edges.



%% ====================
\clearpage
\noindent
$\bullet$ What is the maximum number of $f$ for fixed $n$? \\
\begin{displaymath}
\mbox{e.g. when } n=4.
\end{displaymath}

\hspace*{1in}\\

\noindent
$\bullet$ When all the {\it faces} are bounded with 3 arcs:

\begin{displaymath}
m=\frac{3f}{2} \rightarrow f=\frac{2m}{3} \rightarrow n-m+\frac{2m}{3}=2
   \rightarrow m=3n-6.
\end{displaymath}

\hspace*{1in}\\

\noindent
$\bullet$ In general
\begin{displaymath}
m \le 3n-6\\
\end{displaymath}

\hspace*{1in}\\

\noindent
$\bullet$ So,\\


\begin{displaymath}
a(G)=\frac{2m}{n} \le \frac{6n-12}{n} = 6-\frac{12}{n},
\end{displaymath}

\hspace*{1in}\\

\noindent
$\bullet$ and hence,\\

\begin{displaymath}
a(G) < 6.
\end{displaymath}

\hspace*{1in}\\

\noindent
$\bullet$ Therefore

\begin{displaymath}
\kappa(G), \lambda(G) \le 5.
\end{displaymath}


%% ====================
\clearpage
\noindent
$\bullet$ Dual graph of $G$ \hspace{1in}$\Rightarrow$ $G^{*}$

\begin{itemize}
\item[1.] Choose a point $v^{*}$ inside each face of $G$.
\item[] \hspace*{1in} $\Downarrow$
\item[] These points will be nodes of $G^{*}$
\item[]
\item[2.] Draw a line $e^{*}$ so that it cross each edge $e$ of $G$,
          and joins the node $v^{*}$ in the face $f$ adjoining $e$.
\end{itemize}


%% ====================
\clearpage
\noindent
$\bullet$ Edge connectivity of plane graph\\

\begin{table}[hbtp]
\begin{center}
\begin{tabular}{l l c}
if      & $G^{*}$ has a loop                       & $\lambda = 1$ \\
else if & $G^{*}$ has a multiple arc               & $\lambda = 2$ \\
else if & $G^{*}$ has a face surrounded by 3 edges & $\lambda = 3$ \\
else if & $G^{*}$ has a face surrounded by 4 edges & $\lambda = 4$ \\
else    & \hspace{1in}                             & $\lambda = 5$ \\
\end{tabular} 
\end{center}
\end{table}


%% ====================
\clearpage
\begin{itemize}
\item[$\Box$] {\bf Diameter, Radius, Center and  Periphery\\ of a Graph}\\
\end{itemize}
\begin{itemize}
\item[$\cdot$] From now on, we consider undirected graph.
\item[$\cdot$] What we imagine is a trafic network with weight being 
               capacity of the road, but taking no notice of weights 
               for the time being.\\
\end{itemize}
\begin{itemize}
\item {\bf Distance} $d(x,y)$:
   \begin{itemize}
   \item the minimumu number of arcs from node $x$ to node $y$.
      \begin{itemize}
      \item this fulfill the axiom of distance, i.e.,
         \begin{itemize}
         \item $d(x,x)=0$
         \item $d(x,y)=0$ $\Rightarrow$ $x=y$  %%koko 
         \item $d(x,y) = d(y,x)$
         \item $d(x,y)+d(y,z) > d(x,z)$\\
         \end{itemize}
      \end{itemize}
   \end{itemize}
\clearpage
\item {\bf Eccentricity} (Longest distance)
   \begin{itemize}
   \item for $\forall x$, $\forall y$, $e(x) = \max d(x,y)$ %%koko
         is called {\it eccentricity} \\
   \end{itemize}
\item {\bf Radius} $R(G)$
   \begin{itemize}
   \item for $\forall x$ $\min(e(x))$\\
   \end{itemize}
\item {\bf Diameter} $D(G)$
   \begin{itemize}
   \item for $\forall x$ $\max(e(x))$\\
   \end{itemize}
\item {\bf Center}
   \begin{itemize}
   \item Points where $e(x)=R(G)$ are called {\it center}.\\
   \end{itemize}
\item {\bf Periphery}
   \begin{itemize}
   \item Points where $e(x)=D(G)$ are called {\it periphery}.
   \end{itemize}
\end{itemize}


%% ====================
\clearpage
\noindent
{\bf $\bullet$ An example}\\

\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=term-cap-3.eps,width=16cm,height=4cm}
 \end{center}
\end{figure}

\begin{table}[hbtp]
\begin{center}
\begin{tabular}{l c c c c c c c c c c} \hline \hline
$\sigma$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline
$e(v)$   & 7 & 7 & 6 & 5 & 4 & 4 & 5 & 6 & 6 & 7 \\ \hline\hline
\end{tabular} 
\end{center}
\end{table}

\begin{center}
$\Downarrow$\\

\hspace*{1in}\\

$R(G)=4$\\
$D(G)=7$\\
center $\Rightarrow$ 5, 6\\
periphery $\Rightarrow$ 1, 2, 10
\end{center}

%% ====================
\clearpage

\begin{itemize}
\item Adjacency matrix $A$
\end{itemize}
\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=term-cap-2.eps,width=8cm,height=4cm}
 \end{center}
\end{figure}

\begin{itemize}
\item What does $ {( A^n ) }_{ij}$ mean?
   \begin{itemize}
   \item the number of path from node $i$ to node $j$ whose distance is $n$. 
   \item example
   \item[] $
         A=\
         \left(      
         \begin{array}{ccccc}
         0 & 1 & 0 & 0 & 0\\
         1 & 0 & 1 & 0 & 1\\
         0 & 1 & 0 & 1 & 1\\
         0 & 0 & 1 & 0 & 2\\
         0 & 1 & 1 & 2 & 0
         \end{array}
         \right)
         $
   \item[] $A^2=$ ?
   \item[] $A^3=$ ?
   \item[] ------------
   \item[] $(A^3)_{2,3}=7$ \hspace{.2in}$\Rightarrow$ \hspace{.2in}
               the number of path from 2 to 3 \\
               \hspace*{2.2in}whose distance is 3.\\
   \end{itemize}
\item $S(r) = A + A^2 + A^3 + \cdots + A^r$.
   \begin{itemize}
   \item the number of path from $i$ to $j$ whose distance is 
         less than or equal to $r$. 
   \end{itemize}
\end{itemize}

%% ========== Contents ==========
\clearpage
\noindent
$\Box$ {\bf How to obtain $D(G)$?}\\

\begin{itemize}
\item Step 1
   \begin{itemize}
   \item Calculate $A^r$ and $S(r)$ starting with $r=1$ by incrementing $r$.
   \end{itemize}
\item Step 2
   \begin{itemize}
   \item When all the non-diagonal element are zero at first time, then $r$
         is  $D(G)$.
   \end{itemize}
\end{itemize}

%% ========== Contents ==========
\clearpage
\noindent
$\Box$ {\bf Terminal Capacity}\\

\noindent
A path whose length is $i$ is worth than a length $i+1$ path.\\

\hspace*{1in}$\Downarrow$\\

\noindent
Devide every element $A^i$ by ${\eta}^{i}$, where usually $\eta = n$

\hspace*{1in}$\Downarrow$\\

\noindent
$
W(r)=(A/\eta)+(A/\eta)^2+(A/\eta)^3+\cdots+(A/\eta)^n
$\\

\hspace*{1in}$\Downarrow$\\

\noindent
Summation of the $i$-th column of $W(r)$:\\
$
(W(r))_{1k}+(W(r))_{2k}+(W(r))_{3k}+\cdots +(W(r))_{nk}
$\\

\hspace*{1in}$\Downarrow$ implies\\

\noindent
the number of paths to node $k$ whose lenght is less than $r$
from every node of the Graph,\\

\hspace*{1in}$\Downarrow$ called\\

\noindent
Terminal Capacity of Length $r$


%% ========== Contents ==========
\clearpage
\noindent
$\Box$ {\bf An Example of Terminal Capacity}\\

\begin{displaymath}
W(3)=\frac{1}{125}\left(
\begin{array}{ccccc}
 5 & 28 &  6 &  3 &  6 \\
18 & 17 & 37 & 18 & 40 \\
 6 & 37 & 21 & 44 & 48 \\
 3 & 18 & 44 & 27 & 70 \\
 6 & 40 & 48 & 70 & 36
\end{array}
\right)
\end{displaymath}

\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=term-cap-2.eps,width=8cm,height=8cm}
 \end{center}
\end{figure}


%% ========== Contents ==========
\clearpage
\noindent
$\Box$ Terminal Capacity for $n \rightarrow \infty$ \\

\noindent
Recall the equation:

\begin{displaymath}
1+x+x^2+x^3\cdots=\frac{1}{1-x}\\
\end{displaymath}

\noindent
This corresponds to Matrix relation of:

\begin{displaymath}
(I-X)(I+X+X^2+X^3\cdots)=I\\
\end{displaymath}

\noindent
So, when $\vert I-X \vert \ne 0$\\

\begin{displaymath}
X+X^2+X^3 \cdots=(I-X)^{-1} - I\\
\end{displaymath}

\noindent
Therefore

\begin{displaymath}
W(\infty)=\{I-(A/\eta)\}^{-1} - I\\
\end{displaymath}

\noindent
Note that this does not require calculation of power of matrix. 

%% Figure

%% ========== Contents ==========
\clearpage

\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=terminal-cap.eps,width=16cm,height=16cm}
 \end{center}
\end{figure}

\clearpage
\begin{table}[hbtp]
\begin{center}
\begin{tabular}{c r c} \hline \hline
city & population & capacity \\ \hline
A &   3000,000 & ? \\
B &   4000,000 & ? \\
C &   6000,000 & ? \\
D &   8000,000 & ? \\
E & 1,0000,000 & ? \\
F &   7000,000 & ? \\ \hline \hline
\end{tabular} 
\end{center}
\end{table}


\begin{displaymath}
A=\left(
\begin{array}{cccccc}
0.00 & 0.16 & 0.00 & 0.00 & 0.00 & 0.60 \\
0.16 & 0.00 & 0.30 & 0.00 & 0.06 & 0.50 \\
0.00 & 0.30 & 0.00 & 0.30 & 0.60 & 0.00 \\
0.00 & 0.00 & 0.30 & 0.00 & 0.00 & 0.00 \\
0.00 & 0.06 & 0.60 & 0.00 & 0.00 & 1.00 \\
0.60 & 0.50 & 0.00 & 0.00 & 1.00 & 0.00 \\
\end{array}
\right)
\end{displaymath}

\begin{displaymath}
W(3)=\left(
\begin{array}{cccccc}
0.0112 & 0.0357 & 0.0034 & 0.0022 & 0.0115 & 0.1068 \\
0.0357 & 0.0111 & 0.0536 & 0.0062 & 0.0303 & 0.0925 \\
0.0034 & 0.0536 & 0.0164 & 0.0643 & 0.1134 & 0.0222 \\
0.0022 & 0.0062 & 0.0643 & 0.0198 & 0.1388 & 0.0223 \\
0.0115 & 0.0303 & 0.1134 & 0.1388 & 0.0556 & 0.1798 \\
0.1068 & 0.0925 & 0.0222 & 0.0223 & 0.1798 & 0.0454 \\
\end{array}
\right)
\end{displaymath}


\begin{displaymath}
W(\infty)=\left(
\begin{array}{cccccc}
0.0117 & 0.0363 & 0.0038 & 0.0026 & 0.0190 & 0.1074 \\
0.0363 & 0.0118 & 0.0541 & 0.0068 & 0.0319 & 0.0933 \\
0.0038 & 0.0541 & 0.0174 & 0.0653 & 0.1146 & 0.0240 \\
0.0026 & 0.0068 & 0.0653 & 0.0210 & 0.1400 & 0.0241 \\
0.0190 & 0.0319 & 0.1146 & 0.1400 & 0.0597 & 0.1812 \\
0.1074 & 0.0933 & 0.0240 & 0.0241 & 0.1812 & 0.0487 \\
\end{array}
\right)
\end{displaymath}


%% ========== Contents ==========
\clearpage
\noindent
{\bf $\Box$ Markov Chain}\\

\noindent
Random Walk

\begin{itemize}
\item A drunken walk:\\
      An example of the 1-diomensional random walk.\\
   \begin{itemize}
   \item Denote the place at which he can stop by with\\
         \hspace{1in}$ E_1, E_2, \cdots, E_6 $\\
   \item The initial position: $E_4$\\
   \item Every time he steps to either right, left or stay unmoved\\
         with the probability 1/2, 1/3, 1/6, respectively.\\
   \item If he arrives at either $E_1$ or $E_6$, he stays there\\
         \hspace{1in}$E_1$ and $E_6$ $\Rightarrow$ absorbing state.\\
   \item Then\\
      \begin{itemize}
      \item Which of the $E_1$ and $E_6$, 
            he is more likely to arrive first?\\
      \item The probabilities of his position
         \begin{itemize}
         \item after one step $\Rightarrow$ $(0,0,1/2, 1/6, 1/3, 0)$
         \item after two steps $\Rightarrow$ $(0,1/4,1/6, 1/36, 1/9, 1/9)$
         \end{itemize}
      \end{itemize}
   \end{itemize}
\clearpage
\item definition\\
   \begin{itemize}
   \item initial position vector\\
         \hspace*{1in}$\mbox{{\bf x}} = (0, 0, 0, 1, 0, 0)$\\
   \item transition matrix\\
         \hspace*{1in}$P = (p_{ij})$\\
         where $p_{ij}$'s are the probability that he moves from $E_i$
         to $E_j$ in one step\\
   \item[]In the drunken example above:
   \end{itemize}
\end{itemize}

\begin{displaymath}
P=\left(
\begin{array}{cccccc}
 1  &  0  &  0  &  0  &  0  &  0  \\
1/2 & 1/6 & 1/3 &  0  &  0  &  0  \\
 0  & 1/2 & 1/6 & 1/3 &  0  &  0  \\
 0  &  0  & 1/2 & 1/6 & 1/3 &  0  \\
 0  &  0  &  0  & 1/2 & 1/6 & 1/3 \\
 0  &  0  &  0  &  0  &  0  &  1  
\end{array}
\right)
\end{displaymath}

\begin{itemize}
\item[] \hspace*{1in}
   \begin{itemize}
   \item The probability that he is at $E_i$ after $k$ steps is
   \item[] \hspace*{1in} $x \cdot P^k$ \\
   \end{itemize}
\item Markov chain is $(P, x)$ where
   \begin{itemize}
   \item $P$ $\Rightarrow$ $n \times n $ transition matrix
   \item $x$ $\Rightarrow$ $1 \times n $ row vector
   \end{itemize}
\clearpage
\item $E_i$ is called {\it states} of the chain.\\
\item Our goal here is to classify these states.\\
\item Assume that we are only concerned whether we can get from a given
      state to another state and if so how long it takes.
         \begin{itemize}
         \item In the drunken example above:
            \begin{itemize}
            \item $E_4$ to $E_1$ with three steps.
            \item $E_4$ to $E_6$ with two steps.
            \item $E_1$ to $E_4$ is impossible.\\
            \end{itemize}
         \end{itemize}
\item[] \hspace*{1in} $\Downarrow$ So,\\
\item our concern is not with the actual value of $p_{ij}$.
      but whether $p_{ij}$'s are non-zero.\\
\item[] \hspace*{1in} $\Downarrow$ So a chain is expressed by a\\
\item directed graph
\end{itemize}


%%%%% TWO Figures  p110


%% ========== Contents ==========
\clearpage
\begin{itemize}
\item We can get from a state $E_1$ to a state $E_j$
      iff there is a path frow $i$ to $j$, and the least possible time is 
      the length of the shortest such path\\
\item[]\hspace*{1in}$\Downarrow$\\
\item A Markov chain in which we can get from any state to any other is 
      called {\it irreducible chain}.\\
\item[]\hspace*{1in}$\Downarrow$ clearly\\
\item A Markov chain is irreducible iff the corresponding directed graph 
      is {strongly connected.}
\end{itemize}


%% ========== Contents ==========
\clearpage
\noindent
$\Box$ Directed Graph Revisit\\

\begin{itemize}
\item Definition
   \begin{itemize}
   \item underlying graph
      \begin{itemize}
      \item when we revome arrows from the directed graph.\\
      \end{itemize}
   \item A digraph is {\it connected} if its underlying graph is 
         a connected graph.\\
   \item A digraph is {\it strongly connected} if, for any two nodes 
         $v$, $w$, there is a paht from $v$ to $j$.
   \end{itemize}
\item[]
\item[] Note that
   \begin{itemize}
   \item every strong connected digraph is connected but not all
         conndected digraph is strong connected.
   \end{itemize}
\end{itemize}

%% FIGURE p101

%% ========== Contents ==========
\clearpage
\begin{itemize}
\item The distinction between 
      a connected and a strongly connected digraph.\\
   \begin{itemize}
   \item Consider the road map of a city, all of whose streets are one-way.\\
   \item If the road map is connected, 
         we can drive from any part of the city to any other, 
         ignoring the direction of the one-way streets.\\
   \item If the map is strongly connected, 
         we can drive from any part of the city to any other, 
         always going the right way down the one-way streets.\\
   \end{itemize}
\item Every one-way system should be strongly connected.\\
\item Then how we can impose a one-way system in such a way 
      that we can drive from any part of the city to any other.
   \begin{itemize}
   \item If, for example, the city consists of two parts connected only 
         by a bridge, then we cannot impose such a one-way system, 
         since whatever direction we give to the bridge, one part of 
         the city must be cut off.
   \end{itemize}
\clearpage
\item Define a graph to be {\it orientable} if each edge of the graph
      can be directed so that the resulting digraph is strongly connected.
   \begin{itemize}
   \item Note that any Eulerian graph is orientable.\\
   \end{itemize}
\item Theorem
   \begin{itemize}
   \item Let $G$ be a connected graph. Then $G$ is orientable iff each edge 
         of $G$ is  contained in at least one cycle.\\
   \end{itemize}
\end{itemize}

%% ========== Contents ==========
\clearpage
\noindent
{\bf $\Box$ A classification of States - 1}\\
\begin{itemize}
\item {\bf Persistent/Transient}
   \begin{itemize}
   \item States to which we keep on retruning however long we continue.\\
         \hspace*{1in}$\Rightarrow$ persistent states
   \item States we visit a few times and never return to\\
         \hspace*{1in}$\Rightarrow$ transient states\\
   \end{itemize}
\item[] in other words,\\
   \begin{itemize}
   \item If the probability of returning to $E_i$ at some later stage is 1\\
         \hspace*{1in}$\Rightarrow$ persistent states (e.g. $E_1$, $E_6$)\\
   \item otherwise\\
         \hspace*{1in}$\Rightarrow$ transient states 
                      (e.g. $E_2 \cdots, E_5$)\\
   \end{itemize}
\end{itemize}

%% ========== Contents ==========
\clearpage

\noindent
{\bf Theorem}
\begin{itemize}
\item $E_j$ is persistent iff the existence of a path from $i$ to $j$ in the
      corresponding graph implies the existence of a path from  $j$ to $i$.\\
\end{itemize}

\noindent
In the example (2) above:
\begin{itemize}
\item[] There is a path from 1 to 4, but no path from 4 to 1,
\item[]\hspace*{1in}$\Downarrow$ thus 
\item[]$E_1$ is {\it transient}, as is $E_3$, \\
       whereas $E_2$, $E_4$, $E_5$ and $E_6$ are {\it persistent.}
\end{itemize}


%% ========== Contents ==========
\clearpage
\noindent
{\bf $\Box$ A classification of States - 2}\\
\begin{itemize}
\item {\bf Periodicity}\\
   \begin{itemize}
   \item A Markov chain is {\it periodic} of period $t$ $(t\ne 1)$
         if it is possible to return to $E_i$ only after a period of time 
         that is a multiple of $t$.\\
   \item If no such $t$ exists $\Rightarrow$ {\it aperiodic}.
   \end{itemize}
\end{itemize}


%% ========== Contents ==========
\clearpage
\noindent
{\bf $\Box$ A classification of States - 3}\\
\begin{itemize}
\item {\bf Ergodicity}\\
   \begin{itemize}
   \item A state is {\bf ergodic} if it is both persistent and aperiodic.\\
   \item A Markov chain is {\bf ergodic} if every state is ergodic.
   \end{itemize}
\end{itemize}

%% ========== Contents ==========
\clearpage
\noindent
{\bf $\Box$ Exercise}\\

\begin{itemize}
\item In the drunken walk example:
   \begin{itemize}
   \item suppose $E_6$ ejects him as soon as he gets there.
      \begin{itemize}
      \item Write down the transition matrix.
      \item Draw the corresponding digraph.
      \item Classify the states.\\
      \end{itemize}
   \item How about if both eject him?
   \end{itemize}
\end{itemize}


\end{LARGE}
\end{document}
