\documentclass{article} \usepackage{amsmath} \usepackage[dvipdfm]{graphicx} \usepackage[dvipdfm,designi,tight]{web} % dvipsone, dvips, pdftex, dvipdfm \usepackage{exerquiz} \title{Introduction to Graph Theory} \author{J. E. Fields} \subject{Graph Theory} \keywords{} \university{Southern Connecticut State University\\ Department of Mathematics} \email{fields@southernct.edu} \version{1.0} \copyrightyears{2001-2003} \marginsize{1in}{1in}{1in}{1in} \screensize{8.5in}{11in} \newcounter{probno}[section] \renewcommand{\theprobno}{\thesection.\arabic{probno}} % % Define a problem environment with its own counter. \newenvironment{problem}{% \renewcommand\exlabel{Problem} \renewcommand\exlabelformat{\textbf{\exlabel\ \theprobno.}} \renewcommand\exsllabelformat {\noexpand\textbf{\exlabel\ \theprobno.}} \renewcommand\exrtnlabelformat{$\blacktriangleleft$} \renewcommand\exsecrunhead{Solutions to Problems} \begin{exercise}[probno]} {\end{exercise}} % Define an example environment with no counter \newenvironment{example}{% \renewcommand\exlabel{Example} \renewcommand\exlabelformat{\textbf{\exlabel.}} \renewcommand\exrtnlabelformat{$\square$} \SolutionsAfter \begin{exercise}[0]}% {\end{exercise}} \begin{document} \maketitle \tableofcontents \listoffigures \newpage \section{Introduction} A {\em graph} is a mathematical object that captures the notion of connection. Most people are familiar with the children's puzzle of trying to connect 3 utilites (water, telephone and electricity) to 3 houses without having any of the ``wires'' cross. See Figure~\ref{f:3_utils}. \begin{figure}[!htbp] \begin{center} \includegraphics[scale=.5]{3_utils.eps} \end{center} \caption{The 3 utilities problem.} \label{f:3_utils} \end{figure} A somewhat less familiar, but actually more germaine example (this is widely thought to be how graph theory originated) is found in a puzzle that was posed by the townsfolk of K\"{o}nigsberg, Prussia in the early 1700's. K\"{o}nigsberg (now known as Kaliningrad) was built largely on an island in the Pregel river, this island sits near where two branches of the river join, and the borders of the town spread over to the banks of the river as well as a nearby promontory. Between these four land masses, seven bridges had been erected. See Figure~\ref{f:kon}. \begin{figure}[!hbtp] \includegraphics[scale=.4]{konigsberg.eps} \caption[K\"{o}nigsberg]{The town of K\"{o}nigsberg and its seven bridges.} \label{f:kon} \end{figure} The townspeople supposedly posed the question ``Is it possible to take a walk through town, crossing each of the seven bridges just once, and ending up wherever you started?'' The famous swiss mathematician Leonhard Euler (pronounced ``Oiler'') heard of the problem, solved it (it's not possible) and in the process invented Graph Theory. Since the question involved the connection of land masses by bridges, Euler realized that all the points on the island (for example) were equivalent as far the question was concerned, so the island as well as the banks and the promontory could be represented with single points. In Figure~\ref{f:graph} we see what K\"{o}nigsberg and its bridges look like in Euler's abstracted version. \begin{figure}[!hbtp] \begin{center} \includegraphics{kon_graph.eps} \end{center} \caption[K\"{o}nigsberg as a graph]{The graph that corresponds to K\"{o}nigsberg and its seven bridges.} \label{f:graph} \end{figure} \clearpage \section{Notation} To formalize our discussion of graph theory, we'll need to introduce some terminology. A graph $G$ is a pair of sets $V$ and $E$ together with a function $f:E \mapsto V\times V$. The elements of $V$ are the {\em vertices} (a.k.a. nodes or points) of $G$. The elements of $E$ are the {\em edges} of $G$. The function $f$ sends an edge to the pair of vertices that are its endpoints, thus $f$ is known as the {\em edge--endpoint function}. This terminology is unfortunate since $f$ is generally only a relation. Informally, we usually forget about the edge--endpoint function and simply identify $E$ with a sub-multiset of $V\times V$. We need to think of $E$ as a sub-multiset because there may be more than one edge between a given pair of vertices. Connections generally come in two forms, those that are non-directional (e.g. the bridges of K\"{o}nigsberg) and those that have an implicit direction (e.g. the utility hookups -- water flows from the utility {\em to} one's home, not vice versa). To distinguish these two cases we really need to define two different kinds of graphs. We will use the term {\em graph} to indicate a graph where the connections are non-directional -- if we need to really emphasize this point we might say {\em ordinary graph} or {\em undirected graph}. For situations in which the connections are directional, we use the term {\em digraph} -- a contraction of {\em directed graph}. Note that in our original definition, the codomain of the edge--endpoint function was the set $V\times V$ of ordered pairs of vertices, or, equivalently in the informal version, we think of $E$ as consisting of a sub-multiset of these ordered pairs. Now we can explain the comment that $f$ is only a relation. Suppose $e_k$ is an edge in an ordinary graph that connects vertices $v_i$ and $v_j$, then {\em both} of the ordered pairs $(v_i,v_j)$ and $(v_j,v_i)$ should be images of $e_k$ under $f$ -- i.e. $f$ is many-valued. The problem discussed in the previous paragraph {\em could} be assuaged by making the codomain of $f$ be the set of all 2-subsets of $V$, but this introduces its own problem: shouldn't it be possible for a vertex to be connected to itself? The answer is that for some problem types one would like to have graphs that allow for the possibility of a vertex being connected to itself. Such edges are called {\em loops} in the graph $G$ and while $(v_i,v_i)$ is an element of $V\times V$, it is not true that $\{v_i,v_i\}$ is a 2-subset of $V$. The most general definition for an ordinary graph would be to identify $E$ with a sub-multiset of the set of all 2-sub-multisets of $V$ (multisets containing either 2 distinct elements of $V$ or 2 copies of the same element). In practice, such a high level of correctness is not necessary. In many applications, one deals with graphs that have neither loops nor multiple copies of the same edge (these are known as {\em parallel edges}). Such graphs are called {\em simple graphs}. All in all, there are four types of graphs we'd like to distinguish. \begin{enumerate} \item Graphs (no restrictions on loops and parallel edges) \item Simple graphs (may {\em not} have loops or parallel edges) \item Digraphs (no restrictions) \item Simple digraphs (no loops, no parallel edges) \end{enumerate} Note that in a simple digraph edges that run between the same vertices but in opposite directions are not considered parallel. \begin{figure}[!hbtp] \begin{center} \includegraphics[scale=1]{ns_graph.eps} \end{center} \caption[Undirected graph]{An undirected graph without restrictions. % Graphs such as this may have loops and parallel edges. } \label{f:ns_graph} \end{figure} \begin{figure}[!hbtp] \begin{center} \includegraphics[scale=1]{und_graph.eps} \end{center} \caption[Simple undirected graph]{A simple undirected graph. % Graphs of this type may not have loops or parallel edges. } \label{f:und_graph} \end{figure} \begin{figure}[!hbtp] \begin{center} \includegraphics[scale=1]{ns_digraph.eps} \end{center} \caption[Directed graph]{A non-simple directed graph.} \label{f:ns_digraph} \end{figure} \begin{figure}[!hbtp] \begin{center} \includegraphics[scale=1]{digraph.eps} \end{center} \caption[Simple directed graph]{A simple directed graph. Note % that edges having the same endpoints but going in opposite directions % are allowed.} \label{f:digraph} \end{figure} \clearpage \begin{quiz}*{qz:graph-l} Answer each of the following. \begin{questions} \item Can there be edges having the same endpoints in a simple digraph? \begin{answers}2 \Ans1 Yes &\Ans0 No \end{answers} \item Can there be edges having the same endpoints in a simple (undirected) graph? \begin{answers}2 \Ans0 Yes &\Ans1 No \end{answers} \end{questions} \end{quiz}\quad\ScoreField{qz:graph-l}\eqButton{qz:graph-l} \noindent Answers: \AnswerField{qz:graph-l} \newpage \section{A compendium of graphs} Certain graphs occur frequently enough that they deserve names. A {\em complete graph} on $n$ vertices is a simple (undirected) graph having the maximum possible number of edges. Complete graphs are denoted $K_n$ (probably because complete is spelled with a `K' in German). The complete graphs on 1 through 5 vertices are shown in Figure~\ref{f:K_n}. \begin{figure}[!hbtp] \begin{center} \includegraphics[scale=.5]{complete_graphs.eps} \end{center} \caption[Some complete graphs]{The complete graphs $K_n$ for $1 \leq n \leq 5$.} \label{f:K_n} \end{figure} \clearpage \begin{quiz}*{qz:graph-2} Answer each of the following. \begin{questions} \item How many edges are there in a complete graph on 5 vertices? \begin{answers}4 \Ans0 none & \Ans0 5 & \Ans1 10 & \Ans0 all \end{answers} \item Are there parallel edges in a complete graph? \begin{answers}2 \Ans0 Yes &\Ans1 No \end{answers} \item How many edges are there in general in a complete graph that has $x$ vertices? \newline \RespBox{x*(x-1)/2}{4}{.001}01\hfill %\CorrAnsButton{x*(x-1)/2}%\kern1bp\sqTallyBox \end{questions} \end{quiz}\quad\ScoreField{qz:graph-2}\eqButton{qz:graph-2} \newpage In certain situations, graphs which have connections that only go between 2 ``clumps'' of vertices are studied. For example, a famous problem in discrete math is the assignment problem in which workmen are assigned to operate machines. Each person can only competently operate some subset of the machines. There is a graph that is used in solving the problem, the vertices fall into 2 groups, the people and the machines -- edges are placed between a person and the machines s/he can operate. A more whimsical version of this problem is known as the ``Marriage problem'' -- in a small town, there are several young women and young men of the appropriate age to marry. Each woman has a list of men who she would find acceptable as a spouse. Is it possible for a matchmaker to pair-up these people so that each women gets a husband she finds acceptable? Graphs such as those involved in the assignment problem are called bipartite. A graph $G$ is {\em bipartite} if there is a partition of $V(G)$ into two disjoint sets and there are no edges such that both of their endpoints are in one of these sets. A {\em complete bipartite graph} is a bipartite graph having the maximum possible number of edges. Complete bipartite graphs are denoted $K_{m,n}$ where $m$ and $n$ are the sizes of the sets in the partition. Some complete bipartite graphs are shown in Figure~\ref{f:K_mn}. \begin{figure}[!hbtp] \begin{center} \includegraphics[scale=.75]{complete_bipartite.eps} \end{center} \caption[Some complete bipartite graphs]{The complete bipartite % graphs $K_{3,3}$ and $K_{2,4}$.} \label{f:K_mn} \end{figure} \clearpage Another interesting family of graphs consists of $n$ dimensional hypercubes. In two dimensions, this means a square. In three dimensions, an ordinary cube. The ``hyper'' prefix only becomes appropriate in dimension greater than 3. This family of graphs is defined recursively. To make a $n$-dimensional hypercube, take two copies of an $n-1$-dimensional hypercube and connect corresponding vertices in the copies. See Figure~\ref{f:hypercubes}. \begin{figure}[!hbtp] \begin{center} \includegraphics[scale=.5]{hypercubes.eps} \end{center} \caption[Hypercube graphs]{The first several hyercubes -- dimensions % 1 through 4.} \label{f:hypercubes} \end{figure} \clearpage Our finally example of a ``named'' graph is the Petersen graph. This graph is interesting for many reasons, one of which is the way it can be constructed from another graph. Consider the complete graph $K_5$ which has 10 edges. The vertices of the Petersen graph correspond to those edges (of $K_5$), two vertices are connected by an edge in the Petersen graph if the corresponding edges in $K_5$ meet at a vertex (of $K_5$). \begin{figure}[!hbtp] \begin{center} \includegraphics[scale=.5]{petersen.eps} \end{center} \caption[The Petersen graph]{The Petersen graph, named for its % discoverer, the Danish mathematician Julius Petersen.} \label{f:petersen} \end{figure} \clearpage \section{Isomorphism} The word {\em isomorphism} cames from Greek roots, its meaning is roughly ``equal shapes.'' We say that two graphs are isomorphic if there is a function $\phi$ that maps the vertex set of one graph to the vertex set of the other; additionally, this function must be a bijection (one-to-one and onto) and it must respect the edge-endpoint relation. That is, if $v_i$ and $v_j$ are connected by some number of edges in the first graph then $\phi(v_i)$ and $\phi(v_j)$ are connected by the same number of edges in the second. In a more formal treatment we would require $\phi$ to map both the vertex set {\em and} the edge set, and the phrase ``respect the edge-endpoint relation'' would mean that \[ f(e) = v \; \iff \; f(\phi(e)) = \phi(v) \] \noindent where $f$ denotes the edge endpoint relation. There are a great number of properties called {\em graph invariants} that can be used to decide whether graphs are {\em not} isomorphic. For instance if two graphs have a different number of nodes, they cannot possibly be isomorphic ($\phi$ couldn't be a bijection in that case). Similarly, two isomorphic graphs must have the same number of edges. Clearly these conditions are not sufficient. Consider the two graphs in Figure~\ref{f:non-iso_graphs}, they both have 5 vertices and 5 edges, but obviously there is something different about them. \begin{figure}[!hbtp] \begin{center} \includegraphics[scale=.5]{non-iso_graphs.eps} \end{center} \caption[Non-isomorphic graphs.]{Non-isomorphic graphs that have the % same number of vertices as well as edges.} \label{f:non-iso_graphs} \end{figure} \clearpage One feature that can be used to distinguish the graphs in Figure~\ref{f:non-iso_graphs} is the degrees of their vertices. The {\em degree} of a vertex $v$ in a graph $G$ is the number of edges that are incident with it. (Note that since a loop is incident twice with the same vertex, it will add two to the degree of that vertex.) There is a vertex having degree 1 in the graph on the left in the figure, whereas all the vertices in the right-hand graph have degree 2. \begin{figure}[!hbtp] \begin{center} \includegraphics[scale=.3,angle=-90]{graph_iso.eps} \end{center} \caption[Isomorphic?]{Are these pairs of graphs isomorphic?} \label{f:graph_iso} \end{figure} \begin{shortquiz} Which of the pairs of graphs in Figure~\ref{f:graph_iso} are isomorphic? \begin{answers}[qz:graph_iso]{4} \Ans0 none &\Ans1 1st but not 2nd &\Ans0 2nd but not first &\Ans0 both \end{answers} \begin{solution} \begin{quote} The first pair of graphs are isomorphic (both are the Petersen graph). The second pair can be differentiated, the left graph has only even cycles, the graph on the right has some odd cycles. \end{quote} \end{solution} \end{shortquiz} \clearpage Another graph invariant that is easily used to detect the difference between non-isomorphic graphs is the number of cycles of a given length. A {\em cycle} in a graph is a path along the edges of $G$ that begins and ends in the same place and never hits a vertex (other than the initial one) more than once -- it must also not cross any edge more than once. Consider the non-isomorphic graphs from the quiz. The graph on the left in Figure~\ref{f:graph_iso} has only even length cycles, whereas the graph on the right has cycles of length 5. There are many other properties of graphs that are invariants. \end{document}