\documentclass{article}% \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{graphicx}% \setcounter{MaxMatrixCols}{30} %TCIDATA{OutputFilter=latex2.dll} %TCIDATA{Version=5.00.0.2552} %TCIDATA{CSTFile=40 LaTeX article.cst} %TCIDATA{Created=Thursday, August 21, 2008 14:03:59} %TCIDATA{LastRevised=Wednesday, September 17, 2014 10:53:13} %TCIDATA{} %TCIDATA{} %TCIDATA{} %TCIDATA{Language=American English} \newtheorem{theorem}{Theorem} \newtheorem{acknowledgement}[theorem]{Acknowledgement} \newtheorem{algorithm}[theorem]{Algorithm} \newtheorem{axiom}[theorem]{Axiom} \newtheorem{case}[theorem]{Case} \newtheorem{claim}[theorem]{Claim} \newtheorem{conclusion}[theorem]{Conclusion} \newtheorem{condition}[theorem]{Condition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{criterion}[theorem]{Criterion} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{exercise}[theorem]{Exercise} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{notation}[theorem]{Notation} \newtheorem{problem}[theorem]{Problem} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{remark}[theorem]{Remark} \newtheorem{solution}[theorem]{Solution} \newtheorem{summary}[theorem]{Summary} \newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}} \begin{document} \title{Math 443/543 Graph Theory Notes 2: Transportation problems} \author{David Glickenstein} \maketitle \section{Readings} This is based on Chartrand Chapter 3 and Bondy-Murty 18.1, 18.3 (part on Closure of a Graph). \section{K\"{o}nigsberg bridge problem and Eulerian graphs} See the figure for the graph corresponding to the K\"{o}nigsberg bridge problem.% %TCIMACRO{\FRAME{dtbpF}{2.6675in}{2.0033in}{0pt}{}{}{konigsberg2.wmf}% %{\special{ language "Scientific Word"; type "GRAPHIC"; %maintain-aspect-ratio TRUE; display "USEDEF"; valid_file "F"; %width 2.6675in; height 2.0033in; depth 0pt; original-width 9.5998in; %original-height 7.1996in; cropleft "0"; croptop "1"; cropright "1"; %cropbottom "0"; filename 'pics/Konigsberg2.wmf';file-properties "XNPEU";}} }% %BeginExpansion \begin{center} \includegraphics[ natheight=7.199600in, natwidth=9.599800in, height=2.0033in, width=2.6675in ]% {pics/Konigsberg2.wmf}% \end{center} %EndExpansion The problem is whether one can traverse each edge exactly once. Here is the answer: No. Here is the argument. We must start and stop at one of the vertices (possibly the same one). In particular, there must be at least one of the vertices B,C,D of degree three which is neither the start nor the stop point. Since it has degree three, the walker can enter along one edge (the walker does not start there) then leave by a second edge, then return by the last edge. Then the walker cannot move again. However, since this means the walker must stop there, we have a contradiction with the fact that we do not stop at that vertex. \begin{definition} An \emph{eulerian circuit} (or eulerian tour) is a circuit containing all of the edges and vertices of the (multi-)graph. An \emph{eulerian trail} is trail containing all of the edges and vertices of the (multi-)graph. A graph which contains an eulerian circuit is called an \emph{eulerian graph} and a graph containing an eulerian trail that is not also a circuit is called a \emph{traversable graph}. \end{definition} Recall that circuits and trails traverse each edge only once (but may traverse vertices any number of times). \newline We can characterize both eulerian circuits and trails: \begin{theorem} A (multi-)graph is eulerian if and only if it is connected and every vertex has even degree. A (multi-)graph is traversable if and only if it is connected and exactly two vertices have odd degree. \end{theorem} \begin{proof} The two statements are proven almost the same way, so we only prove the first statement. If a graph $G$ is eulerian, then it contains an eulerian circuit $C$ which begins and ends at a vertex $v\in V\left( G\right) .$ Since the circuit contains all vertices, there is a trail that connects any two vertices (a subset of the circuit $C$), and hence a path (by removing repeated occurrences of any vertices). Thus $G$ is connected. Now consider a vertex $u\neq v.$ Since the circuit neither begins nor ends at $u,$ each time $u$ is traversed, there must be an edge entering and an edge exiting. Thus the edges occur in pairs for each time the circuit visits $u$ and $u$ must have even degree. For the vertex $v,$ every time it is visited other than the first and last time, there must be an edge entering and an edge exiting. Add to this one for the initial edge leaving and one for the last edge entering, $v$ must have even degree too. (Note how this is changed for the second statement in the theorem). For the converse, we must show that an eulerian circuit exists if the graph $G$ is connected and every vertex has an even degree. Pick an initial vertex $v$ and begin constructing a trail $T$ until it can no longer be extended. The trail $T$ must be a circuit (i.e., end at $v$) since if it ended at any other vertex, that vertex would have odd degree since it has entered and exited an even number of times and then finally entered with nowhere to go. Since all vertices have even degree, $T$ is a circuit. Now we must extend $T$ to be eulerian, i.e., to traverse all of the edges. Consider the graph $G^{\prime}$ gotten by removing the edges in the circuit $T.$ Notice that $G^{\prime}$ also has the property that each vertex has even degree. If there are no edges in $G^{\prime},$ then $T$ is eulerian. Otherwise, there must be an edge connected to a vertex $v^{\prime}$ which is covered by $T$ (since $G$ is connected). We may now construct a new circuit $T^{\prime}$ in the same way, beginning and ending at $v^{\prime}.$ Furthermore, we may append $T^{\prime}$ to the trail $T$ to get a new circuit $T^{\prime\prime}$ which covers more edges. We may then continue the procedure of removing the edges of $T^{\prime\prime}$ in $G$ until we get an eulerian circuit. We know this procedure will terminate since we are always adding edges to the trail $T$ and their are a finite number of edges in $G.$ \end{proof} Example 3.2 gives an interesting application of eulerian graphs. Also note that the proof gives an algorithm for finding eulerian circuits and trails. \section{Salesman problem and hamiltonian graphs} The traveling salesman problem is the following: A salesman has to visit each city in his territory. The cities are connected by certain highways (or even by certain plane routes). Is it possible to plan a round trip so that he visits each city exactly once? \begin{definition} A cycle containing all of the vertices of $G$ is called a \emph{hamiltonian cycle}. A graph containing a hamiltonian cycle is called a \emph{hamiltonian graph}. \end{definition} It turns out that the problem of finding a hamiltonian cycle is NP-complete, which essentially means it is quite difficult. First, here is a condition satisfied by a hamiltonian graph: \begin{theorem} If $G$ is a hamiltonian graph, then for any nonempty, proper subset $S\subset V\left( G\right) ,$ $G-S$ has at most $\left\vert S\right\vert $ components. \end{theorem} \begin{proof} Let $\omega\left( G\right) $ denote the number of components of $G.$ We know $G$ contains a hamiltonian cycle $C,$ and for a cycle, we have that \[ \omega\left( C-S\right) \leq\left\vert S\right\vert , \] since removing one vertex leaves it connected, removing a second produces two components, removing a third produces another component, etc. However, since $C$ is a subgraph of $G$ which contains all of the vertices of $G,$ we see that \[ \omega\left( G-S\right) \leq\omega\left( C-S\right) \] (since $G-S=C-S$ union some edges). \end{proof} Example: Show this graph is not hamiltonian (From BM):% %TCIMACRO{\FRAME{dtbpF}{4.1594in}{3.1233in}{0pt}{}{}{graph3-3.wmf}% %{\special{ language "Scientific Word"; type "GRAPHIC"; %maintain-aspect-ratio TRUE; display "USEDEF"; valid_file "F"; %width 4.1594in; height 3.1233in; depth 0pt; original-width 9.5998in; %original-height 7.1996in; cropleft "0"; croptop "1"; cropright "1"; %cropbottom "0"; filename 'pics/graph3-3.wmf';file-properties "XNPEU";}}}% %BeginExpansion \begin{center} \includegraphics[ natheight=7.199600in, natwidth=9.599800in, height=3.1233in, width=4.1594in ]% {pics/graph3-3.wmf}% \end{center} %EndExpansion We give one sufficient condition for a graph to be hamiltonian. \begin{theorem} Suppose $G$ is a graph of order $p\geq3$ such that $\deg v\geq p/2$ for every $v\in V\left( G\right) .$ Then $G$ is hamiltonian. \end{theorem} Note that this is certainly not necessary, since we may consider a simple cycle, in which ever vertex has degree 2 but it is certainly hamiltonian. \begin{proof} If $p=3,$ then every vertex has degree larger than $3/2,$ so $G$ is the complete graph (a triangle) and that is hamiltonian. Now assume $p\geq4.$ Let $P=u_{0},u_{1},\ldots,u_{k}$ be a path which visits the most vertices (there may be several of these paths, but all visit the same number of vertices). We notice the following: \begin{enumerate} \item All vertices adjacent to $u_{0}$ must be in $P,$ since otherwise we could make $P$ larger. The same is true for $u_{k}.$ \item The path must have $k+1\geq p/2+1$ since $\deg u_{0}\geq p/2.$ \item There exists a number $i,$ $1\leq i\leq k,$ such that $u_{0}$ is adjacent to $u_{i}$ and $u_{k}$ is adjacent to $u_{i-1}.$ Suppose this were not the case, then for each $u_{i}$ adjacent to $u_{0}$ (there are at least $p/2$ of these), there is another vertex not adjacent to $u_{k},$ which means there are $p/2+1$ vertices (including $u_{k}$) not adjacent to $u_{k}.$ However, this is impossible since it would mean that $\deg u_{k}\leq p-\left( p/2+1\right)