Hamiltonian Circuit And Euler Circuit

Running head: GRAPH THEORY AND TREES
GRAPH THEORY AND TREES
Name of the Student
Name of the University
Author Note

Essay: Graphs for modeling real world situations
In this particular essay a graph is produced by a school bus pickup situation as described in
details below. Let a school bus picks up students from different locations and transports all
the students to the school. Let, the bus starts from the depot at location D and picks up five
students S1, S2, S3, S4, S5 and then transports them to the location of school S. Now, there
are many roads and alleys connecting the locations of students and schools, but, the school
bus cannot fit into alleys and thus can only pass through the roads. The different road lengths
which connects the locations are given in the following table in kilometres.
Road segments Length (in km)
D-S 25
D-S1 3
D-S2 4
S1-S3 6
S3-S 5
S4-S5 7
S3-S4 3
D-S5 10
S2-S5 6
S4-S 9
Table 1: Road segment lengths
The above lengths can easily visualized by an un-directed graph as given below.

Graph of Bus route
In the above graphs the vertices are presented in blue circles which are the locations of Bus
depot, school and pickup locations of five students. There are a total of 7 vertices in this
graph. The edges are the road segments connecting the locations or the vertices which have
the weights as given in table 1. Now, the bus starts from D and reaches to S by going through
all the locations of students S1 to S5 at least once for picking up all. The graph has a total of
10 edges with highest weight corresponds of D-S edge and lowest edge corresponding to D-
S1 and S4-S3 branch. Now, from this graph many problems can be formulated like if there
exists one or more paths which passes through every vertices exactly once. Another
informative question can be, finding the minimum cost of the path from D to S that connects
every other nodes in the graph. This particular question can be economically beneficial as
finding the minimum length of travelling from source to destination can save the cost of the

trip every day. Dijkstra and A* algorithms are popular iterative algorithm for finding
minimum cost path between two nodes in a graph.
Now, there are many paths that joins starting point of the above graph D and ending point S
some of which is D-S, D-S1-S3-S, D-S2-S5-S4-S etc. However, this paths are not circuit as
the ending and starting nodes are different. In the graph the circuit are the paths in which the
ending and starting nodes are same like D-S1-S3-S-S, D-S5-S2-D, D-S5-S4-S-D. Now, the
Euler circuit is the circuit in which every edge of a graph is used exactly once. The
Hamiltonian circuit is a circuit in which every vertices of the graph is visited exactly once.
The only exception of the starting node as to become a circuit the starting node must be
visited twice. The above graph has no Euler or Hamiltonian circuit however, many sub-
graphs can be extracted from the graph that is Euler and Hamiltonian circuit. For, an example
if the sub-graph S4-S3-S is extracted then this becomes an Euler circuit as every edge is
visited only once. Now, the circuit S4-S3-S-S4 is a Hamiltonian circuit also as every vertices
is visited once. The extracted sub-graph S4-S3-S is shown below.
Sub-graph S4-S-S3