\documentclass[10pt]{article}
\usepackage{amssymb,latexsym,amsmath,multicol}
\usepackage{pstricks,pst-node,pst-plot}
\usepackage{multido}
\usepackage{color}

%%%%%%%%%%%
% Margins %
%%%%%%%%%%%
\addtolength{\textwidth}{1.50in}
\addtolength{\textheight}{1.00in}
\addtolength{\evensidemargin}{-0.75in}
\addtolength{\oddsidemargin}{-0.75in}
\addtolength{\topmargin}{-.50in}
\begin{document}
\magstep{100}
\pagestyle{empty}
\sffamily
\huge

\begin{center}
\textbf{Definition}
\end{center}

A graph $G$ consists of a set of vertices $V$ and a set of edges $E$, where an edge is an unordered pair of vertices.

\vfill
\begin{center}
\textbf{Examples}
\begin{enumerate}
\item Computer Networks
\begin{eqnarray*}
V &=& \{ \rm computers \} \\
E &=& \{ \{A,B\} ~|~ \hbox{ computers $A$ and $B$ are networked} \}
\end{eqnarray*}
\vfill
\item Social Networks
\begin{eqnarray*}
V &=& \{ \hbox{Alice, Bob, Chris, Daniel, ...} \} \\
E &=& \{ \{A,B\} ~|~ \hbox{ $A$ and $B$ know each other} \}
\end{eqnarray*}
\vfill

\item  $V = \{ v_1,v_2,v_3,v_4,v_5 \}$ and $E = \{ e_1,e_2,e_3,e_4,e_5,e_6 \}$.
{\Large
\begin{center}
\begin{pspicture}(-4,-4)(4,4)
\psset{unit=3cm,labelsep=2pt}
\cnode*(0,1){3pt}{v1}         %\put(0,1){\circle{.25}} \rput(0,1){a}
\cnode*(.951,.309){3pt}{v2}   %\put(.951,.309){\circle{.25}} \rput(.951,.309){b}
\cnode*(.588,-.809){3pt}{v3}  %\put(.588,-.809){\circle{.25}} \rput(.588,-.809){c}
\cnode*(-.588,-.809){3pt}{v4} %\put(-.588,-.809){\circle{.25}} \rput(-.588,-.809){d}
\cnode*(-.951,.309){3pt}{v5}  %\put(-.951,.309){\circle{.25}} \rput(-.951,.309){e}
\ncline[linewidth=1pt]{-}{v1}{v4}\lput*(.6){$e_1$}
\ncline[linewidth=1pt]{-}{v5}{v2}\lput*(.2){$e_2$}
\ncline[linewidth=1pt]{-}{v2}{v4}\lput*(.8){$e_3$}
\ncarc[arcangleA=25,arcangleB=25]{v1}{v3}\lput*(.2){$e_4$}
\ncarc[arcangleA=25,arcangleB=25]{v3}{v1}\lput*(.2){$e_5$}
\nccircle[angleA=-72]{v2}{.5cm}\lput*(.5){$e_6$}
\psset{unit=3.4cm}
\rput(0,1){$v_1$}
\rput(.951,.309){$v_2$}
\rput(.588,-.809){$v_3$}
\rput(-.588,-.809){$v_4$}
\rput(-.951,.309){$v_5$}
\end{pspicture}
\end{center}
}


\end{enumerate}
\end{center}

\newpage
\begin{center}
\textbf{Directed Graphs}
\end{center}

A directed graph or digraph $G$ consists of a set of vertices $V$ and a set of directed edges $E$, where an edge is an {\em ordered} pair of vertices.

\vfill
\begin{center}
\textbf{Examples}
\end{center}
\begin{enumerate}
\item Functional Digraphs.  Let $f$ be a function from $X$ to $Y$.
\begin{eqnarray*}
V &=& X \cup Y \\
E &=& \{ (x,y)\in X\times Y ~|~ f(x) = y \}
\end{eqnarray*}

{\large
\newcommand{\dedge}[3]{\psline{->}#1#2 \psline#1#3 \rput#1{$\bullet$}}
\begin{center}
\begin{pspicture}(0,-.5)(2.5,3)
\dedge{(0,1)}{(.3,1.6)}{(.5,2)}  \rput(0,.8){6} 
\dedge{(.5,0)}{(.8,.6)}{(1,1)}   \rput(.5,-.2){3}   
\dedge{(1.5,0)}{(1.2,.6)}{(1,1)} \rput(1.5,-.2){12}
\dedge{(1,1)}{(.7,1.6)}{(.5,2)}  \rput(1.2,1){13}
\rput(.5,2){$\bullet$} \rput(.5,2.2){1} \psarc{-}(.5,2.4){.4}{-85}{265} \psarc{->}(.5,2.4){.4}{-85}{100}
\end{pspicture}
%
\begin{pspicture}(0,-.5)(3.5,3)
\dedge{(0,1)}{(.3,1.6)}{(.5,2)}   \rput(0,.8){5}
\dedge{(1,1)}{(.7,1.6)}{(.5,2)}   \rput(1,.8){9}
\dedge{(.5,2)}{(1.1,2)}{(1.5,2)}  \rput(.5,2.2){10}
\dedge{(1.5,2)}{(2.1,2)}{(2.5,2)} \rput(1.5,2.2){14}
\rput(2.5,2){$\bullet$} \rput(2.5,2.2){2}
\psplot{-42}{222}{x cos 40 mul 42.5 add x sin .5 mul 2.35 add} \psline{<-}(1.4,2.85)(1.6,2.85)
\end{pspicture}
%
\begin{pspicture}(0,-.5)(1.5,3)
\rput(.5,2){$\bullet$} \rput(.5,2.2){7} \psarc{-}(.5,2.4){.4}{-85}{265} \psarc{->}(.5,2.4){.4}{-85}{100}
\end{pspicture}
%
\begin{pspicture}(0,-.5)(2,3)
\dedge{(0,1)}{(.3,1.6)}{(.5,2)}  \rput(0,.8){11} 
\dedge{(.5,0)}{(.8,.6)}{(1,1)}   \rput(.5,-.2){8}   
\dedge{(1.5,0)}{(1.2,.6)}{(1,1)} \rput(1.5,-.2){4}
\dedge{(1,1)}{(.7,1.6)}{(.5,2)}  \rput(1.2,1){15}
\rput(.5,2){$\bullet$} \rput(.5,2.2){16} \psarc{-}(.5,2.4){.4}{-85}{265} \psarc{->}(.5,2.4){.4}{-85}{100}
\end{pspicture}
\end{center}
}

\item Game Theory
\begin{eqnarray*}
V &=& \{ \hbox{possible game states} \} \\
E &=& \{ (A,B) ~|~ \hbox{ state $B$ can be achieved from state $A$} \}
\end{eqnarray*}
\end{enumerate}
\vfill


\newpage
\begin{center}
\textbf{Problems}
\end{center}

\begin{enumerate}
\item[$\bullet$] \textbf{Eulerian Path} - Can we draw a given graph without lifting our pencil from the paper and without repeating edges?
\begin{center}
\begin{pspicture}(-2,-2)(2,2.5)
\psset{unit=2cm,labelsep=2pt}
\cnode*(0,1){3pt}{v1}         %\put(0,1){\circle{.25}} \rput(0,1){a}
\cnode*(.951,.309){3pt}{v2}   %\put(.951,.309){\circle{.25}} \rput(.951,.309){b}
\cnode*(.588,-.809){3pt}{v3}  %\put(.588,-.809){\circle{.25}} \rput(.588,-.809){c}
\cnode*(-.588,-.809){3pt}{v4} %\put(-.588,-.809){\circle{.25}} \rput(-.588,-.809){d}
\cnode*(-.951,.309){3pt}{v5}  %\put(-.951,.309){\circle{.25}} \rput(-.951,.309){e}
\ncline{-}{v1}{v4}
\ncline{-}{v5}{v2}
\ncline{-}{v2}{v4}
\ncarc[arcangleA=25,arcangleB=25]{v1}{v3}
\ncarc[arcangleA=25,arcangleB=25]{v3}{v1}
\nccircle[angleA=-72]{v2}{.5cm}
\end{pspicture}
\hspace{50pt}
\begin{pspicture}(-2,-2)(2,2)
\psset{unit=2cm,labelsep=2pt}
\cnode*(0,1){3pt}{v1}         %\put(0,1){\circle{.25}} \rput(0,1){a}
\cnode*(.951,.309){3pt}{v2}   %\put(.951,.309){\circle{.25}} \rput(.951,.309){b}
\cnode*(.588,-.809){3pt}{v3}  %\put(.588,-.809){\circle{.25}} \rput(.588,-.809){c}
\cnode*(-.588,-.809){3pt}{v4} %\put(-.588,-.809){\circle{.25}} \rput(-.588,-.809){d}
\cnode*(-.951,.309){3pt}{v5}  %\put(-.951,.309){\circle{.25}} \rput(-.951,.309){e}
\ncline{v1}{v4}
\ncline{v5}{v2}
\ncline{v1}{v5}
\ncline{v5}{v4}
\ncline{v3}{v2}
\ncline{v2}{v1}
\ncline{v3}{v4}
\end{pspicture}
\end{center}
\vfill

\item[$\bullet$] \textbf{Hamiltonian Path} - Can we visit each vertex once and only once using only the edges of a graph?

\begin{center}
\begin{pspicture}(-2,-2)(2,2.5)
\psset{unit=2cm,labelsep=2pt}
\cnode*(0,1){2pt}{v1}         
\cnode*(.951,.309){2pt}{v2}   
\cnode*(.588,-.809){2pt}{v3}  
\cnode*(-.588,-.809){2pt}{v4}
\cnode*(-.951,.309){2pt}{v5} 
\psset{unit=1.5cm,labelsep=2pt}
\cnode*(0,1){2pt}{v6}         
\cnode*(.951,.309){2pt}{v7}   
\cnode*(.588,-.809){2pt}{v8}  
\cnode*(-.588,-.809){2pt}{v9}
\cnode*(-.951,.309){2pt}{v10} 
\psset{unit=1cm,labelsep=2pt}
\cnode*(0,-1){2pt}{v11}         
\cnode*(.951,-.309){2pt}{v12}   
\cnode*(.588,.809){2pt}{v13}  
\cnode*(-.588,.809){2pt}{v14}
\cnode*(-.951,-.309){2pt}{v15} 
\psset{unit=.5cm,labelsep=2pt}
\cnode*(0,-1){2pt}{v16}         
\cnode*(.951,-.309){2pt}{v17}   
\cnode*(.588,.809){2pt}{v18}  
\cnode*(-.588,.809){2pt}{v19}
\cnode*(-.951,-.309){2pt}{v20}
\ncline{v1}{v2} 
\ncline{v2}{v3}
\ncline{v3}{v4} 
\ncline{v4}{v5} 
\ncline{v5}{v1} 
\ncline{v1}{v6} 
\ncline{v2}{v7} 
\ncline{v3}{v8} 
\ncline{v4}{v9} 
\ncline{v5}{v10}

\ncline{v6}{v13} 
\ncline{v13}{v7} 
\ncline{v7}{v12} 
\ncline{v12}{v8} 
\ncline{v8}{v11} 
\ncline{v11}{v9} 
\ncline{v9}{v15} 
\ncline{v15}{v10} 
\ncline{v10}{v14} 
\ncline{v14}{v6} 
 
\ncline{v11}{v16} 
\ncline{v12}{v17} 
\ncline{v13}{v18} 
\ncline{v14}{v19} 
\ncline{v15}{v20} 

\ncline{v16}{v17} 
\ncline{v17}{v18} 
\ncline{v18}{v19} 
\ncline{v19}{v20}
\ncline{v20}{v16} 
 
\end{pspicture}
\hspace{50pt}
\begin{pspicture}(-3,-2)(3,2.5)
\psset{unit=1cm,labelsep=2pt}
\cnode*(0,-2){2pt}{v1}         
\cnode*(-.75,-1){2pt}{v2}   
\cnode*(.75,-1){2pt}{v3}  
\cnode*(-3,0){2pt}{v4}
\cnode*(-1.8,0){2pt}{v5} 
\cnode*(0,0){2pt}{v6}         
\cnode*(1.8,0){2pt}{v7}   
\cnode*(3,0){2pt}{v8}  
\cnode*(-.75,1){2pt}{v9}
\cnode*(.75,1){2pt}{v10} 
\cnode*(0,2){2pt}{v11}         

\ncline{v1}{v2} \ncline{v1}{v3} \ncline{v1}{v4} \ncline{v1}{v8}
\ncline{v2}{v5} \ncline{v2}{v6}
\ncline{v3}{v6} \ncline{v3}{v7} 

\ncline{v11}{v10} \ncline{v11}{v9} \ncline{v11}{v4} \ncline{v11}{v8}
\ncline{v9}{v5} \ncline{v9}{v6}
\ncline{v10}{v6} \ncline{v10}{v7} 

\end{pspicture}
\end{center}
\vfill

\newpage
\item[$\bullet$] \textbf{Isomorphism Problem} - When are two graphs the ``same"?
{\Large
\begin{center}
\begin{pspicture}(-2,-2)(2,2)
\psset{unit=1.75cm}
\cnode*(-1,1){3pt}{v1}
\cnode*(1,1){3pt}{v2}
\cnode*(1,-1){3pt}{v3}
\cnode*(-1,-1){3pt}{v4}
\rput(-1,1.2){$a$}
\rput(1.2,1){$b$}
\rput(1,-1.2){$c$}
\rput(-1.2,-1){$d$}
\psset{unit=.75cm}
\cnode*(-1,1){3pt}{v5}
\cnode*(1,1){3pt}{v6}
\cnode*(1,-1){3pt}{v7}
\cnode*(-1,-1){3pt}{v8}
\rput(-1,1.4){$e$}
\rput(1.4,1){$f$}
\rput(1,-1.4){$g$}
\rput(-1.4,-1){$h$}
\ncline{v1}{v2}
\ncline{v2}{v3}
\ncline{v3}{v4}
\ncline{v4}{v1}
\ncline{v1}{v5}
\ncline{v5}{v6}
\ncline{v6}{v7}
\ncline{v7}{v8}
\ncline{v8}{v5}
\ncline{v2}{v6}
\ncline{v3}{v7}
\ncline{v4}{v8}
\end{pspicture}
\hspace{50pt}
\begin{pspicture}(-2,-2)(2,2)
\psset{unit=1.75cm}
\cnode*(0,1){3pt}{v1}
\cnode*(1,0){3pt}{v2}
\cnode*(0,-1){3pt}{v3}
\cnode*(-1,0){3pt}{v4}
\psset{unit=2.1cm}
\rput(0,1){$a$}
\rput(1,0){$c$}
\rput(0,-1){$h$}
\rput(-1,0){$d$}
\psset{unit=1.24cm}
\cnode*(1,1){3pt}{v5}
\cnode*(1,-1){3pt}{v6}
\cnode*(-1,-1){3pt}{v7}
\cnode*(-1,1){3pt}{v8}
\psset{unit=1.5cm}
\rput(1,1){$b$}
\rput(1,-1){$f$}
\rput(-1,-1){$g$}
\rput(-1,1){$e$}
\ncline{v1}{v5}
\ncline{v2}{v5}
\ncline{v2}{v6}
\ncline{v6}{v3}
\ncline{v3}{v7}
\ncline{v4}{v7}
\ncline{v4}{v8}
\ncline{v1}{v8}
\ncline{v1}{v4}
\ncline{v8}{v5}
\ncline{v3}{v2}
\ncline{v7}{v6}
\end{pspicture}
\end{center}
}
\vfill
\item[$\bullet$] \textbf{Shortest Route} - Find the shortest path between two vertices

{\Large
\begin{center}
\begin{pspicture}(4,4)
\cnode*(0,0){3pt}{v1} \rput(-.3,-.3){A}
\cnode*(2,.25){3pt}{v2}
\cnode*(3,1){3pt}{v3}
\cnode*(1,1){3pt}{v4}
\cnode*(3,4){3pt}{v5} \rput(3.3,4.3){B}
\cnode*(2.25,1.5){3pt}{v6}
\cnode*(.5,3){3pt}{v7}
\cnode*(2,3){3pt}{v8}
\ncline{v1}{v2} \ncline{v1}{v4} \ncline{v1}{v7}
\ncline{v2}{v3} \ncline{v2}{v6}
\ncline{v4}{v6} \ncline{v4}{v8}
\ncline{v5}{v6} \ncline{v5}{v3}
\ncline{v7}{v8} \ncline{v5}{v7}
\ncline{v8}{v5}
\end{pspicture}
\end{center}
}

\vfill
\newpage
\item[$\bullet$] \textbf{Assignment Problem} - How do you assign tasks to individuals so that each person can do the task assigned to them?  How can you minimize time required to complete all tasks?
{\large
\begin{center}
\begin{pspicture}(6,4)
\rput(0,3){\rnode{alice}{Alice}}
\rput(3,3){\rnode{bill}{Bill}}
\rput(6,3){\rnode{chris}{Chris}}
\rput(0,0){\rnode{job1}{Job 1}}
\rput(2,0){\rnode{job2}{Job 2}}
\rput(4,0){\rnode{job3}{Job 3}}
\rput(6,0){\rnode{job4}{Job 4}}
\ncline{-}{alice}{job1}\lput*(.2){10}
\ncline{-}{alice}{job2}\lput*(.3){8}
\ncline{-}{alice}{job4}\lput*(.2){7}
\ncline{-}{bill}{job1}\lput*(.2){9}
\ncline{-}{bill}{job3}\lput*(.2){7}
\ncline{-}{chris}{job1}\lput*(.65){6}
\ncline{-}{chris}{job2}\lput*(.75){8}
\ncline{-}{chris}{job3}\lput*(.5){9}
\ncline{-}{chris}{job4}\lput*(.5){8}

\end{pspicture}
\end{center}
}
\vfill

\item[$\bullet$] \textbf{Network Flow Problems} - Determine the least expensive way to transport product from surplus sites to demand sites.

{\normalsize
\begin{center}
\begin{pspicture}(-2,-2)(2,2.5)
\psset{unit=1.75cm,labelsep=2pt}
\cnodeput(0,1){a}{a}         %\put(0,1){\circle{.25}} \rput(0,1){a}
\cnodeput(.951,.309){b}{b}   %\put(.951,.309){\circle{.25}} \rput(.951,.309){b}
\cnodeput(.588,-.809){c}{c}  %\put(.588,-.809){\circle{.25}} \rput(.588,-.809){c}
\cnodeput(-.588,-.809){d}{d} %\put(-.588,-.809){\circle{.25}} \rput(-.588,-.809){d}
\cnodeput(-.951,.309){e}{e}  %\put(-.951,.309){\circle{.25}} \rput(-.951,.309){e}
\ncline[linewidth=1pt]{->}{a}{b}\Aput{3}
\ncline[linewidth=1pt]{->}{a}{c}\Aput{2}
\ncline[linewidth=1pt]{->}{a}{d}\Bput{1}
\ncline{<-}{b}{c}\Aput{4}
\ncline{<-}{c}{d}\Aput{2}
\ncline{<-}{d}{e}\Aput{1}
\ncline[linewidth=1pt]{->}{e}{a}\Aput{4}
\psset{unit=2.3cm}
\rput(0,1){4}
\rput(.951,.309){-12}
\rput(.588,-.809){6}
\rput(-.588,-.809){-8}
\rput(-.951,.309){10}
\end{pspicture}
\end{center}
}
\vfill
\newpage
\item[$\bullet$] \textbf{Planar Graphs} - Can a given graph be drawn without 
any pair of edges crossing?  Applications to chip design.

\begin{center}
\begin{pspicture}[.5](3,3)
\cnode*(0,2){3pt}{v1}
\cnode*(2,2){3pt}{v2}
\cnode*(2,0){3pt}{v3}
\cnode*(0,0){3pt}{v4}
\cnode*(1,3){3pt}{v5}
\cnode*(3,3){3pt}{v6}
\cnode*(3,1){3pt}{v7}
\cnode*(1,1){3pt}{v8}
\ncline{v1}{v2}
\ncline{v2}{v3}
\ncline{v3}{v4}
\ncline{v4}{v1}
\ncline{v1}{v5}
\ncline{v5}{v6}
\ncline{v6}{v7}
\ncline{v7}{v8}
\ncline{v8}{v5}
\ncline{v2}{v6}
\ncline{v3}{v7}
\ncline{v4}{v8}\end{pspicture}
\hspace{50pt}
\begin{pspicture}[.5](-2,-2)(2,2)
\psset{unit=1.75cm}
\cnode*(-1,1){3pt}{v1}
\cnode*(1,1){3pt}{v2}
\cnode*(1,-1){3pt}{v3}
\cnode*(-1,-1){3pt}{v4}
\psset{unit=.75cm}
\cnode*(-1,1){3pt}{v5}
\cnode*(1,1){3pt}{v6}
\cnode*(1,-1){3pt}{v7}
\cnode*(-1,-1){3pt}{v8}
\ncline{v1}{v2}
\ncline{v2}{v3}
\ncline{v3}{v4}
\ncline{v4}{v1}
\ncline{v1}{v5}
\ncline{v5}{v6}
\ncline{v6}{v7}
\ncline{v7}{v8}
\ncline{v8}{v5}
\ncline{v2}{v6}
\ncline{v3}{v7}
\ncline{v4}{v8}
\end{pspicture}
\end{center}
\vfill

\item[$\bullet$] \textbf{Chromatic Numbers} - What is the minimum number of distinct colors needed to label the vertices of a graph so that no two adjacent vertices are colored the same?
Four Color Theorem.
\begin{center}
\begin{pspicture}(4,4)
\psset{unit=3cm}
\cnode(0,0){10pt}{v1}
\cnode(1,0){10pt}{v2}
\cnode(0,1){10pt}{v3}
\cnode(1,1){10pt}{v4}
\ncline{v1}{v2}
\ncline{v1}{v3}
\ncline{v1}{v4}
\end{pspicture}
\hspace{50pt}
\begin{pspicture}(4,4)
\psset{unit=3cm}
\cnode(0,0){10pt}{v1}
\cnode(1,0){10pt}{v2}
\cnode(0,1){10pt}{v3}
\cnode(1,1){10pt}{v4}
\ncline{v1}{v2}
\ncline{v1}{v3}
\ncline{v1}{v4}
\ncline{v2}{v4}
\ncline{v3}{v4}
\end{pspicture}
\end{center}

\vfill
\newpage

\item[$\bullet$] \textbf{Traveling Salesman Problem} - In what order should you visit cities $c_1,c_2,\ldots ,c_n$ so that you minimize the distance traveled?

\begin{center}
\begin{pspicture}(4,4)
\cnode*(0,0){3pt}{v1}
\cnode*(2,.25){3pt}{v2}
\cnode*(3,1){3pt}{v3}
\cnode*(1,1){3pt}{v4}
\cnode*(3,4){3pt}{v5}
\cnode*(2.25,1.5){3pt}{v6}
\cnode*(.5,3){3pt}{v7}
\cnode*(2,3){3pt}{v8}
\ncline{v1}{v2}
\ncline{v2}{v3}
\ncline{v3}{v4}
\ncline{v4}{v5}
\ncline{v5}{v6}
\ncline{v6}{v7}
\ncline{v7}{v8}
\ncline{v8}{v1}
\end{pspicture}
\hspace{50pt}
\begin{pspicture}(4,4)
\cnode*(0,0){3pt}{v1}
\cnode*(2,.25){3pt}{v2}
\cnode*(3,1){3pt}{v3}
\cnode*(1,1){3pt}{v4}
\cnode*(3,4){3pt}{v5}
\cnode*(2.25,1.5){3pt}{v6}
\cnode*(.5,3){3pt}{v7}
\cnode*(2,3){3pt}{v8}
\ncline{v1}{v2}
\ncline{v2}{v3}
\ncline{v3}{v6}
\ncline{v6}{v5}
\ncline{v5}{v8}
\ncline{v8}{v7}
\ncline{v7}{v4}
\ncline{v4}{v1}
\end{pspicture}
\end{center}
\vfill

\item[$\bullet$] \textbf{Ramsey Numbers} - What is the minimum number of people required to guarantee that there are $m$ people who all know each other or $n$ none of whom know each other

\begin{eqnarray*}
R(m,1) &=& \\
R(2,2) &=& \\
R(2,n) &=& \\
R(3,3) &=& \\
R(4,4) &=& \\
R(5,5) &=& 
\end{eqnarray*}
\vfill
\end{enumerate}


\end{document}
 