PATHS AND CYCLES
Connectivity
Let us consider four connected graphs of Figure 3.1.
G1 is a tree, a minimal connected graph; deleting any edge disconnects it.
G2 cannot be disconnected by the deletion of a single edge, but can be
disconnected by the deletion of one vertex, its cut vertex.
There are no cut edges or cut vertices in G3 , but even so G3 is clearly not
as well connected as G4 , the complete graph on five vertices.
A vertex cut of G is a subset V of V such that G V is disconnected. A
k vertex cut is a vertex cut of k elements.
A complete graph has no vertex cut; in fact, the only graphs which do
not have vertex cuts are those that contain complete graphs as
spanning subgraphs.
If G has at least one pair of distinct nonadjacent vertices, the connectivity
(G) of G is the minimum k for which G has a k vertex cut; otherwise,
we define (G) to be v 1 .
Thus (G) 0 if G is either trivial or disconnected.
G is said to be k connected if (G) k .
All non trivial connected graphs are 1 connected.
A k edge cut is an edge cut of k elements.
If G is nontrivial and E is an edge cut of G , then G E is disconnected;
we then define the edge connectivity (G) of G to be the minimum k for
which G has a k edge cut.
If G is trivial, (G) is defined to be zero.
Thus (G) 0 if G is either trivial or disconnected.
(G) 1 if G is a connected graph with a cut edge.
21
G is said to be k edge connected if (G) k .
All nontrivial connected graphs are 1 edge connected.
Figure 3.1
Paths and Cycles
Many Problems can be modeled with paths formed by traveling along the
edges of graphs. We begin this section by defining the basic terminology of
graph theory that deals with paths.
Definition
A walk is a finite sequence of vertices and edges of the form
x0 x1 , , xn in which adjacent edges are identical or distinct.
Number of edges of a walk is called its length.
A walk in which all the edges are distinct is called a trail.(vertices could
be repeated).
A trail in which all the vertices are distinct is called a path.
A closed path is a cycle.
A closed trail is a circuit.
22
Theorem
There is a simple path between every pair of distinct vertices of a connected
undirected graph.
Eulerian and Hamiltonian Graphs
Introduction
The town of Konigsberg, Russia, was divided into four sections by the branches
of the Pregel River. These four sections included the two regions on the blanks
of the Pregel, Kneiph of Island, and the region between the two branches of the
Pregel. In the 18th century seven bridges connected these regions. Figure 4.2(a)
depicts these regions and bridges.
The townspeople took long walks through town on Sundays. They wondered
whether it was possible to start at some location in the town, travel across all
the bridges without crossing any bridge twice, and return to the starting
point.
C
D
A
B
Figure 3.2(a) : The 18th –Century Town of Konigsberg.
C The Swiss mathematician Leonhard Euler solved this
problem. His solution, published in 1736, may be the first
use of the graph theory. Euler studied this problem using
the multigraph. Obtained when 4 regions are represented
by vertices and the bridges by edges. This multigraph is
A D shown in Figure 4.3 (b).
The problem of traveling across every bridge without
crossing any bridge more than once can be rephrased in
terms of this model. The question becomes: Is there a
B simple circuit in this multigraph that contains every edge?
Figure 3.2 (b)
23
Eulerian Graph
A connected graph G is Eulerian if there exists a closed trail
containing every edge of G . Such a trail is an Eulerian trail.
Note that this definition requires each edge to be traversed once and once
only.
A non-Eulerian graph G is semi-Eulerian if there exists a trail containing
every edge of G . The following are Euerian, semi-Eulerian and non-
Eulerian graphs respectively.
Eulerian Semi-Eulerian Non-Eulerian
Figure 3.4
Theorem 1
A graph G is bipartite if and only if each cycle of G has even length.
Proof: Let G V G , EG be a bipartite graph.
i.e. V (G) V1 V2 and each edge joins an vertex of V1 with a vertex of V 2 .
Now take any cycle of G , say, v1 v2 vm v1 (edges and vertices are
distinct) of length m .
With out loss of generality, we may assume that v1 V1 .
Then v1 v 2 v3 v 4 v m v1
V1 V2 V1 V2 V2 V1
m must be even.
Let G be a graph whose cycles are all of even length. Without loss of
generality we may assume that G is connected.
Take any vertex, say v1 V , and let
V1 : u V | d (v1 , u) is even v1
V2 : V \ V1
so we have, V V1 V2 and any edge joins a vertex of V1 with a vertex V 2
.
24
Lemma
If G is a graph in which the degree of each vertex is at least 2, then G
contain a cycle.
Proof
If G has any loop or multiple edges, then the result is trivial.
Suppose G is a simple graph. Let v be any vertex of G. Choose v1 to be
any vertex adjacent to v. So that for each i 1 choose vi 1 to be any vertex
adjacent to v i except vi 1 .
Then construct a walk v v1 v2 vi 1 vi vi 1 .
Since G has only finitely many vertices we must eventually choose a vertex
that has been chosen before.
If v k is the first such vertex, then that part of the walk lying between
the two occurrences of v k is the required cycle.
Theorem 2
A connected graph G is Eulerian if and only if the degree of each
vertex of G is even.
Proof:
Suppose that P is an Eulerian trail of G.
Whenever P passes through a vertex then there is a contribution of 2
towards the degree of that vertex. Since each edge occurs exactly once in
P, each vertex must have even degree.
Prove by induction on the number of edges of G.(i.e. Assume that the
assertion is true for the graphs whose number of edges are less than number
of edges of G ).
Suppose the degree of each vertex of G is even.
Since G is connected and each vertex has degree at least 2, by the Lemma
1, G contains a cycle C. If C contains every edge of G, then the proof is
completed.
If not, we remove C from G, and form a new possibly disconnected graph
H, where E H || E G , in which each vertex of H still has even degree.
By the induction hypothesis, each component of H has an Eulerian trail.
25
Since each component of H has at least one vertex in common with C, by
connectedness, we have required Eulerian trail of G by following the edges
of C until a non-isolated vertex of H is reached, tracing the Eulerian trail
of the component of H which contains that vertex, and then continuing
along the edges of C until we reach a vertex belonging to another
component of H and so on. (see Figure 4.5)
H
C
Figure 3.5
Corollary 1
A connected graph is Eularian if and only if its set of edges can be
split up into disjoint cycles.
Corollary 2
A connected graph is semi-Eularian if and only if it has exactly two
vertices of odd degree.
Hamiltonian Graph
We have developed necessary and sufficient conditions for existence of
paths and cycles that contain every edge of a multigraph exactly once.
Here we determine whether there exists a closed trail passing exactly once
through each vertex of G .
Note that such a trail must be a cycle (except when G is a null graph). Such
a cycle is a Hamiltonian cycle and G is a Hamiltonian graph.
A non-Hamiltonian graph G is semi-Hamiltonian if there exists a path
passing through every vertex.
The following are Hamiltonian, semi-Hamiltonian and non-Hamiltonian
graphs respectively.
Hamiltonian 26
Semi-Hamiltonian Non-Hamiltonian
Theorem 3 (Ore, 1960).
If G is a simple graph with n 3 vertices, and if degv degw n for
each pair of non-adjacent vertices v and w , then G is Hamiltonian.
Examples
1. A connected graph need not have a Hamiltonian path. eg. Tree.
2. K 2 has non-cyclic Hamiltonian path; if n 2 , K n has a Hamiltonian
cycle.
3. For a graph G with n vertices, n 3 ; having a Hamiltonian circuit is
equivalent to having a cycle C n as a sub graph.
Remark
If all the vertices have sufficiently high degrees then a Hamiltonian path
exists.
n
e.g. If G has n vertices, and degree of each vertex is at least , then there
2
is a Hamiltonian cycle.
Corollary 1
If G is a connected simple graph with n vertices where n 3 , then G
n
has a Hamiltonian cycle if the degree of each vertex is at least .
2
Applications
Many problems can be modeled using graphs with weights assigned to their
edges. Problems involving distances can be modeled by assigning
distances between cities to the edges, problems involving flight time can
be modeled by assigning travel time between cities to the edges and
problems involving traveling cost can be modeled by assigning traveling
cost between cities to the edges. Graphs with weights assigned to their
edges are called weighted graphs.
Weighted graphs are used to model computer networks. Communication
costs, the response times of the computers over these lines, or the distance
between computers, can also be studied using weighted graphs.
Several types of problems involving weighted graphs arise frequently.
Determining the path of least length between two vertices in a network is
one such problem.
The length of a path in a weighted graph is the sum of the weights of the
edges of the path. Then the path of least length, between two given vertices
is the shortest path.
27
Shortest Path Problem
There are several different algorithms that can be used to find the
shortest path between two vertices in a weighted graph.
An algorithm discovered by the Dutch Mathematician E. Dijkstra, in 1959,
is called Dijkstra’s Algorithm.
Example 1
Find the shortest path from a to z of the following weighted graph.
Label vertex a with 0 and all the other vertices with . Use notation
L0 (a) 0 , L0 (v) , for these vertices before any iterations have been taken
place. In each iteration circle the vertex of smallest labeling.
0b 5 d0 b 5 d0 b 5 0d
4 6 4 6 4 6
0a 8 z 0a 1 8 z 8 z
1 2 0 2 0 0a 1 2 0
2 3 2 3 2 3
c 10 e c 10 e c 10 e
0 0 0
28
b 5 d
b 5 0d
4 6
4 6 z
a 8 z a 1 8 2
1 2 0
2 3 2 3
c 10 e c 10 e
b 5 0d
b 5 0d
4 6 4 6
a 1 8 z z
2 a 1 8 2
2 3 2 3
c 10 e c e
10
The Shortest path from a to z is a, c, b, d , e of length 13.
Alternating Method
Suppose that we have a ‘map’ of the form shown below, in which the letters
A-L refer towns that are connected by roads. If the lengths of these roads
are as marked, what is the length of the shortest path from A to L?
Note that the numbers in the diagram need not refer to the lengths of the
roads, but could refer to the times taken to travel along them, or the costs
of doing so. Thus, if we have an algorithm for solving this problem in its
original formulation, then this algorithm can also be used to give the
quickest or cheapest route.
B D G J
2 3 5
3 1 5
4 5
9 2 H 9 L
A
E
2 6 1 6 3
C 9 F 2 I 2 K
29
Note that the upper bound for the answer can easily be obtained by taking
any path from A to L and calculating its length. For example, the path
A B D G J L has total length 18, and so the length of the
shortest path cannot exceed 18.
Method of Solving
Move across the graph from left to right.
First assign temporary labeling Lt (V ) to each vertex V , which is the
distance from A to V .
Then make permanent the smallest of the temporary labeling.
Take L( A) 0 .
Step 1
Label all the vertices adjacent to A.
Lt ( B) L( A) 3 0 3 3 .
Lt ( E) L( A) 9 0 9 9 .
Lt (C ) L( A) 2 0 2 2 .
Make permanent C; L(C) 2 .
Step 2
Label all the vertices adjacent to C.
Lt ( E) L(C) 10 2 6 8.
Lt ( F ) L(C) 9 2 9 11.
List all the temporary labeling;
Lt ( B) 3 , Lt ( E ) 8 , Lt ( f ) 11 .
Make permanent B; L( B) 3 .
Step 3
Label all the vertices adjacent to B.
So the Shortest path has length 17 and the path is
A B E H F I K l.
30
The Chinese Postman Problem
A postman wishes to deliver letters, covering the least possible total distance
and returning to his starting point. He must obviously traverse each road in
his route at least once, but should avoid covering too many roads more than
once.
This problem can be reformed in terms of a weighted graph, where the graph
corresponds to the network of roads, and the weight of each edge is the length of
the corresponding road. In this reformulation, the requirement is to find a closed
walk of minimum total weight that includes each edge at least once. If the graph
is Eulerian, then any Eulerian trail is a closed walk of the required type. Such an
Eulerian trail can be found by Fleury’s algorithm. If the graph is not Eulerian,
then the problem is much harder, although an efficient algorithm is known. To
illustrate the ideas involved we look at special types of graphs, in which exactly
two vertices have odd degrees.
Example 2
A postman collects his mail from one of the locations A,B,C,D,E deliver his mail
and return to the starting location. Find the minimum distance he has to traverse
in order to deliver all the mail. Also, at which locations he has to start his duties
in order to complete the entire job in traveling minimum distance.
B 5 C Since vertices B and E are the only vertices of
3 5 odd degrees, we can find a semi-Eulerian trail from B
A 8 14 10 D to E covering each edge exactly once. In order to return
9 to the staring point, covering the least possible
4
6 distance, we now find the shortest path from E to B
F E
using one of the algorithms described above.
The solution of the Chinese postman problem
is then obtained by taking this shortest path B C
A D
31
F E
E F A B , together with the original semi-
Eulerian trail, giving a total distance of 13 64 77 .
Note that, if we combine the shortest path and the
semi-Eulerian trail, we get an Eulerian graph.
Traveling Salesman Problem
Example 3
A
2
6
8 4 A traveling salesman wishes to visit several given cities
B and return to his starting point, covering the least possible
6 E
total distance. For example, suppose there are five cities A,
7 3 8 5 B, C, D and E, and the distances between the cities are
given in the following figure.
C 9 D
To solve this problem we have to find closed cycle of least weight containing all
the vertices. Which equivalent of finding Hamiltonian cycle with least weight.
For example, suppose there are five cities A, B, C, D and E and the distances
between the cities are given as in the following figure. To find the solution to
Traveling Salesman problem, we have to find a Hamiltonian cycle of least weight,
which is A B D E C A of total 26.
32
