(Autonomous)

ESSENTIALS OF PROBLEM SOLVING

Topic: GRAPH ROUTES

Dr. D Khalandar Basha

Associate Professor
INSTITUTE OF AERONAUTICAL ENGINEERING Don’t write or
(Autonomous) place any image
in this area
DUNDIGAL, HYDERABAD - 500 043
Dr. D Khalandar Basha

SYLLABUS

MODULE II GRAPH ROUTES

Eulerian circuit: Konigsberg bridge problem, touring

a graph; Eulerian graphs, Hamiltonian cycles, the
traveling salesman problem; Shortest paths:
Dijkstra’s algorithm, walks using matrices.

Don’t write or place any

image in this area
Dr. D Khalandar Basha

Graph Theory Basics

 Origin of Graph theory: Seven Bridges of Königsberg

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Graph Theory Basics

 Origin of Graph theory: Seven Bridges of Königsberg

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Euler Circuits

Leonhard Euler first discussed and used Euler paths and circuits in 1736.
Rather than finding a minimum spanning tree that visits every vertex of a graph, an
Euler path or circuit can be used to find a way to visit every edge of a graph once
and only once.
 By counting the number of vertices of a graph, and their degree we can determine
whether a graph has an Euler path or circuit.
 classifications and differentiation of graphs according to the connections
between nodes. Don’t write or
place any image
 how the edges relate with the nodes, forming specific sequences.
[Link] in this area
mathforliberalarts/chapter/introduction-euler-paths/
Dr. D Khalandar Basha

Basic Graph Traversals

 The length of any of these tours is defined in terms of the number of edges.
 Traversal (Traveling) through a graph can be
 Walk
 Trails
 Path
 Circuit
 Cycle

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Walk
 When we have a graph and traverse it, then that traverse will be known as a walk.
 A walk is a sequence of vertices so that there is an edge between consecutive
vertices.
 A walk can repeat vertices and edges.
 A walk can be defined as a sequence of edges and vertices of a graph.
 The number of edges which is covered in a walk will be known as the Length of the
walk.
 In a graph, there can be more than one walk.
Don’t write or
 So for a walk, the following two points are important, place any image
in this area
 Edges can be repeated Vertex can be repeated
Dr. D Khalandar Basha

Walk
 For example: In this example, we have a graph, which is described as follows:
 In the above graph, there can be many walks, but some of them
are described as follows:

 1. A, B, C, E, D (Number of length = 4)
 2. D, B, A, C, E, D, C (Number of length = 7)
 3. E, C, B, A, C, E, D (Number of length = 6)

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Walk
 Types of Walks
 There are two types of the walk, which are described as follows:
 Open walk
 Closed walk
 Open Walk:
 A walk will be known as an open walk in the graph theory if the vertices at which
the walk starts and ends are different.
 That means for an open walk, the starting vertex and ending vertex
Don’t write or
 must be different. place any image
in this area
 In an open walk, the length of the walk must be more than 0.
Dr. D Khalandar Basha

Walk
 Closed Walk:
 A walk will be known as a closed walk in the graph theory if the vertices at which
the walk starts and ends are identical.
 That means for a closed walk, the starting vertex and ending vertex must be the
same.
 In a closed walk, the length of the walk must be more than 0.

 The walk will be known as the Trivial walk if length of the walk = 0.
Don’t write or
 In case of the open walk and closed walk, the edges and vertices can be place any image
in this area
repeated.
Dr. D Khalandar Basha

Walk
 Suppose there is a graph, which is described as follows:
 In this graph, there is also a closed walk and an
open walk, which are described as follows:

 Closed walk = A, B, C, D, E, C, A
 Open walk = A, B, C, D, E, C

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Trails
 A trail is a walk with no repeated edges.
 A trail can repeat vertices but not edges.
 A trail can be described as an open walk where no edge is allowed to repeat.
 So for a trail, the following point is important, which is described as follows:
 Vertex can be repeated
 But edges are not allowed to repeat.
 An open trail starts and ends on different vertices.
 A closed trail (circuit) starts and ends on the same vertex.
Don’t write or
 All trails are walks and all circuits are closed walks place any image
in this area
Dr. D Khalandar Basha

Trails

 Node_1 -> Node_2 -> Node_1 -> Node_3 -> Node_4

is an example of a trail as no edges are repeated but
Node_1 is traversed twice.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Circuit
 A circuit is a closed trail; that is, a trail that starts and ends at the same vertex with
no repeated edges though vertices may be repeated.
 A circuit can be described as a closed walk where no edge is allowed to repeat.
 In the circuit, the vertex can be repeated.
 A closed trail in the graph theory is also known as a circuit.
 So for a circuit, the following two points are important, which are
 Edges cannot be repeated
 Vertex can be repeated
Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Circuit
 In the above graph, there is a circuit, which is described
as follows:
 Circuit: A, B, D, C, F, H, C, A

Node_1 -> Node_2 -> Node_3 -> Node_4 -> Node_5 -> Node_3
-> Node_1
is an example of a circuit as no edges are repeated but has
vertices repeated.
Dr. D Khalandar Basha

Path
 A path is a trail with no repeated vertex (or edges).
 A path on n vertices is denoted Pn.
 In graph theory, a path is defined as an open walk in which-
 Neither vertices (except possibly the starting and ending vertices) are
allowed to repeat.
 Nor edges are allowed to repeat.

Don’t write or
 The walk abcde does not repeat any edges. place any image
in this area
Dr. D Khalandar Basha

Cycle
 A closed path in the graph theory is also known as a Cycle.
 A cycle is a type of closed walk where neither edges nor vertices are allowed to
repeat.
 There is a possibility that only the starting vertex and ending vertex are the same
in a cycle.
 So for a cycle, the following two points are important, as follows:
 Edges cannot be repeated
 Vertex cannot be repeated
Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Cycle
 A closed path in the graph theory is also known as a Cycle.
 Traversing a graph such that do not repeat a vertex nor repeat a edge but the
starting and ending vertex must be same
 A cycle on n vertices is denoted Cn.
 A cycle is a type of closed walk where neither edges nor vertices are allowed to
repeat.
 The possibility in a cycle is the starting and ending vertex are the same in a cycle.
 So for a cycle, the following two points are important,
Don’t write or
 Edges cannot be repeated place any image
in this area
 Vertex cannot be repeated
Dr. D Khalandar Basha

Cycle
 Example of a circuit.
 Notice how no edges are repeated in the walk bcgfb,
which makes it definitely a trail, and that the start and
end vertex b is the same which makes it closed.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Summary

Repeated Nodes Repeated Edges Open or Closed

Walk Yes Yes Both
Trails Yes No Open
Path No No Open
Circuit Yes No Closed
Cycle No No Closed

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Summary

Every sequence of edges is a walk.

A walk can be open (start/end vertices different) or
closed (start/end vertices same).
If edges can’t repeat, the walk is a trail.
A closed trail is a circuit.
If vertices can’t repeat, the walk is a path.
A closed path is a cycle.
Walks, paths, trails, circuits and cycles do not need to use every edge or Don’t write or
place any image
every vertex in the graph. in this area
Dr. D Khalandar Basha

Summary

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Summary

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Problems

 State the shortest possible closed trail that starts at H.

 Enter each vertex as a capital letter, separated by commas.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Problems

 State the shortest possible closed trail that starts at H.

 Enter each vertex as a capital letter, separated by commas.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Problems

 finding the best (fastest, shortest, cheapest) route between two destinations from
A to B

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Problems
 The following map shows all possible routes in Mohamad's town.
 Mohamad travels from his home to his friend's house on a daily basis.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Problems
 The graph below shows the time in hours taken to travel between various country
towns.
 Determine the least amount of time needed to
travel between towns P and X.
 State the route that would achieve this by listing
the vertices in order, separated by commas.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Problems
 The graph below shows the time in hours taken to travel between various country
towns.
 Determine the least amount of time needed to
travel between towns P and X.
 State the route that would achieve this by listing
the vertices in order, separated by commas.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Problems
 Example: Given the graph below, find a trail (that is not a path) from a to c, a path
from a to c, a circuit (that is not a cycle) starting at b, and a cycle starting at b.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Problems
 The order in which the edges will be traveled are noted in the following routes.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Touring a Graph : Connected

 Let G be a graph.
 Two vertices x and y are connected if there exists a path from x to y in G.
 The graph G is connected if every pair of distinct vertices is connected.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Connected
 Example: Island City has two islands, a peninsula, and left and right banks, as shown

Don’t write or
It would be impossible to travel every bridge and thenreturn home. place any image
In particular, there is no way to even travel from one side of the river to in this area
the other!
Dr. D Khalandar Basha

Connected
 Theorem Every x − y walk contains an x − y path.
 Let the length L of an x − y walk W.
 For the base case, if L = 0 then the walk does not have any edges and so contains a
singe vertex, that is x = y and so W is a path of length 0.
 Next assume L ≥ 1 and suppose the all walks of length k < L. If W has no repeated
vertex, then it cannot have any repeated edges and so W is an x−y path.
 Otherwise W has a repeated vertex, call it u.
 Then remove all edges and vertices between two appearances of u
Don’t write or
 in the walk, and leave only one copy of u. place any image
in this area
Dr. D Khalandar Basha

Connected
 This will produce a shorter x − y walk W which is contained in W.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Connected

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Maximum vs maximal
 An object X is maximum if it is the largest among all objects under consideration;
that is, |X| ≥ |A| for all A ∈ U.
 An object X is maximal if it cannot be made larger.

 In certain scenarios, the adjectives maximum and maximal may be applied

to the same object; however, this need not be true

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Maximal, Maximum
 The path b c d e f (highlighted on the left) is maximal because we cannot add any
additional vertices and keep it a path.

Don’t write or
 However, it is not maximum since a longer path can be found, namely place any image
in this area
 h g c d e f shown on the right.
Dr. D Khalandar Basha

Graph with a cycle

 Theorem : If every vertex of a graph has degree at least 2 then G contains a cycle
 Proof: Let P be a maximal path in G and let x be an endpoint of P.
 Since P is maximal, it cannot be extended and so every neighbor of x must already
be a vertex of P.
 Since x has degree at least 2, we know there must be another neighbor y of x in V
(P) via an edge not a part of the path.

Don’t write or
place any image
in this area
Then the edge xy completes a cycle with the portion of P from x to y.
Dr. D Khalandar Basha

Eulerian Graphs
 Let G be a graph.
 An eulerian circuit (or trail) is a circuit (or trail) that contains every edge and
every vertex of G.
 If G contains an eulerian circuit it is called eulerian and if G contains an eulerian
trail but not an eulerian circuit it is called semi-eulerian

 Theorem A graph G is eulerian if and only if

 (i) G is connected and
Don’t write or
 (ii) every vertex has even degree. place any image
in this area
Dr. D Khalandar Basha

Eulerian Graphs
 If a vertex is odd, then there is no pairing available and we would eventually get
stuck at that vertex.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Eulerian Graphs
 Note
 Let G be a graph.
 An eulerian circuit (or trail) is a circuit (or trail) that contains every edge and
every vertex of G.
 If G contains an eulerian circuit it is called eulerian and
 if G contains an eulerian trail but not an eulerian circuit it is called semi-eulerian.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Eulerian Graphs
 Note
 A graph G is eulerian if and only if
 (i) G is connected and
 (ii) every vertex has even degree.

 A graph G is semi-eulerian if and only if

 (i) G is connected and
 (ii) exactly two vertices have odd degree.
Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Eulerian Graphs
 Example Consider the graphs, Which ones are eulerian? semi-eulerian? neither?
 Solution:

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Eulerian Graphs
 Example Consider the graphs, Which ones are eulerian? semi-eulerian? neither?
 Solution:
 • Even though the graph is connected, it is neither eulerian nor semi-eulerian since
it has more than two odd vertices (namely, a, b, e, and f).

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Eulerian Graphs
 Example Consider the graphs, Which ones are eulerian? semi-eulerian? neither?

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Eulerian Graphs
 Example Consider the graphs, Which ones are eulerian? semi-eulerian? neither?
 • The graph representing Island City in Example is not connected,
 so it is neither eulerian nor semi-eulerian.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Eulerian Graphs
 Example Consider the graphs, Which ones are eulerian? semi-eulerian? neither?
 The graph representing K¨onigsberg is neither eulerian nor semieulerian since all
four vertices are odd.

 Note that the solution to the K¨onigsberg Bridge Problem is there is no

Don’t write or
way to leave your home, travel across every bridge in the city exactly place any image
in this area
once, and return home!
Dr. D Khalandar Basha

Eulerian Graphs
 Example Consider the graphs, Which ones are eulerian? semi-eulerian? neither?


Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Eulerian Graphs
 Example Consider the graphs, Which ones are eulerian? semi-eulerian? neither?
 The graph in Example is neither eulerian nor semi-eulerian since it is not
connected.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Eulerian Graphs
 Example Consider the graphs, Which ones are eulerian? semi-eulerian? neither?

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Eulerian Graphs
 Example Consider the graphs, Which ones are eulerian? semi-eulerian? neither?

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Eulerian Graphs
 Example Consider the graphs, Which ones are eulerian? semi-eulerian? neither?
 The graph in Example is semi-eulerian since it is connected and exactly two
vertices are odd.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Euler Circuits

EULER PATH
An Euler path is a path that uses every edge in a graph with no repeats.
Being a path, it does not have to return to the starting vertex.
EULER CIRCUIT
An Euler circuit is a circuit that uses every edge in a graph with no repeats.
Being a circuit, it must start and end at the same vertex.
EULER’S PATH AND CIRCUIT THEOREMS
A graph will contain an Euler path if it contains at most two vertices of odd degree.
A graph will contain an Euler circuit if all vertices have even degree
Dr. D Khalandar Basha

Euler Circuits

EXAMPLE
In the graph shown below, there are several Euler paths.

One such path is CABDCB. Don’t write or

place any image
The path is shown in arrows to the right, with the order of edges numbered. in this area
[Link]
mathforliberalarts/chapter/introduction-euler-paths/
Dr. D Khalandar Basha

Euler Circuits

EXAMPLE
The graph below has several possible Euler circuits.

Here’s a couple, starting and ending at vertex A: Don’t write or

place any image
ADEACEFCBA and AECABCFEDA. The second is shown in arrows.
[Link] in this area
mathforliberalarts/chapter/introduction-euler-paths/
Dr. D Khalandar Basha

Euler Circuits

Definition: Euler Path

 A path that travels through every edge of a connected graph once and only once
and starts and ends at different vertices

Don’t write or
place any image
 One Euler path for the above graph is F, A, B, C, F, E, C, D, E in this area
Dr. D Khalandar Basha

Euler Circuits

 This Euler path travels every edge once and only once and starts and ends at
different vertices.
 This graph cannot have an Euler circuit since no Euler path can start and end at
the same vertex without crossing over at least one edge more than once.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Euler Circuits

 Definition: Euler Circuit

 An Euler path that starts and ends at the same vertex.

 One Euler circuit for the above

graph is E, A, B, F, E, F, D, C, E

 This Euler path travels every edge once and only once and starts and Don’t write or
place any image
ends at the same vertex. Therefore, it is also an Euler circuit in this area
Dr. D Khalandar Basha

Euler Circuits

 Euler’s Theorem 1 :
 If a graph has any vertices of odd degree, then it cannot have an Euler circuit.
 If a graph is connected and every vertex has an even degree, then it has at least
one Euler circuit (usually more).
 Euler’s Theorem 2 : If a graph has more than two vertices of odd degree, then it
cannot have an Euler path.
 If a graph is connected and has exactly two vertices of odd degree, then
it has at least one Euler path (usually more). Any such path must start Don’t write or
place any image
at one of the odd-degree vertices and end at the other one. in this area
Dr. D Khalandar Basha

Euler Circuits

 Euler’s Theorem 3 :
 The sum of the degrees of all the vertices of a graph equals twice the number of
edges (and therefore must be an even number).
 Therefore, the number of vertices of odd degree must be even.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Euler Circuits

 Finding Euler Circuits:

 Be sure that every vertex in the network has even degree.
 Begin the Euler circuit at any vertex in the network.
 As the edges choosen, never use an edge that is the only connection to a part of the
network that is not already visited.
 Label the edges in the order that you travel them and continue this until you have
travelled along every edge exactly once and you end up at the starting
vertex. Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Euler Circuits
 Ex. Finding Euler Circuits:
 The graph shown has an Euler circuit since each
vertex in the entire graph is even degree.
 Thus, start at one even vertex, travel over each
vertex once and only once, and end at the starting
point.
 One example of an Euler circuit for this graph is A, E, A, B, C, B, E, C, D, E, F, D, F, A.
 This is a circuit that travels over every edge once and only once and
Don’t write or
starts and ends in the same place. place any image
in this area
 There are other Euler circuits for this graph.
Dr. D Khalandar Basha

Euler Circuits

EULERIAN PATH
An Eulerian path is a path of edges that visit all edges in a graph exactly once.
We can find an Eulerian path on the graph below only if we start at specific nodes.

Don’t write or
place any image
[Link] in this area
But, if the starting point is changed we might not get the desired result.
mathforliberalarts/chapter/introduction-euler-paths/
Dr. D Khalandar Basha

Euler Circuits

EULERIAN CIRCUIT
An Eulerian circuit is an Eulerian path that starts and ends at the same vertex.

In the example, we can see that our graph

does have an Eulerian circuit.
If your graph does not contain an Eulerian
cycle then you may not be able to return
to the start node or you will not be able Don’t write or
place any image
to visit all edges of the graph. [Link] in this area
mathforliberalarts/chapter/introduction-euler-paths/
Dr. D Khalandar Basha

Euler Circuits

EULERIAN CIRCUIT
To support our above statement let’s take another example. This is basically the
same but with some modification. We start from the same point.

Don’t write or
place any image
[Link] in this area
mathforliberalarts/chapter/introduction-euler-paths/
Dr. D Khalandar Basha

Euler Circuits
 The conditions required for a valid Eulerian path/circuit:
UNDIRECTED GRAPH:
 Eulerian circuit - every vertex has an even degree.
 Eulerian path - either every vertex has an even degree or exactly two vertices have
an odd degree.
 DIRECTED GRAPH:
 Eulerian circuit - every vertex has equal indegree and outdegree.
 Eulerian path - at most one vertex has (outdegree) - (indegree) = 1 and
Don’t write or
at most one vertex has (indegree) - (outdegree) = 1, and all other place any image
in this area
vertices have equal in and outdegrees.
Dr. D Khalandar Basha

Euler Circuits
 FINDING AN EULERIAN PATH (DIRECTED GRAPH)
 Step one to finding an Eulerian path is determining if an Eulerian path even exists.
 Recall that for an Eulerian path to exist, at most one vertex has (outdegree) -
(indegree) = 1 and at most one vertex has (indegree) - (outdegree) = 1, and all
other vertices have equal in and outdegrees.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Euler Circuits
 In our above example we have calculated both in and outdegree of each node, and
now we can confirm our conditions for a Eulerian path. No nodes have out[i] - in[i]
> 1 or in[i] - out[i] > 1 and there are just the right amount of start/end nodes.
 Node one is the only node with exactly one extra outgoing edge, so it’s our only
valid start node. Similarly, node six is the only node with exactly one extra
incoming edge, so it will end up being the end node.

Don’t write or
place any image
[Link]
in this area
circuit-in-graphs
Dr. D Khalandar Basha

Algorithms For Eulerian

 Step1: Connectivity Check ( Check if all edges are present in 1 component only)
 Find a node with a degree > 0
 If no node found then Euler graph
 Else Do DFS and mark all nodes in component
 Check if any node with degree > 0 was unutilized
 If True then not a Euler Graph
 Step2: Count odd degree nodes (Use adjacency list)
 Count = 0 => Eulerian Graph
Don’t write or
 Count = 2 => Semi Eulerian Graph place any image
in this area
 Count > 0 => Not Eulerian Graph
Dr. D Khalandar Basha

Algorithms For Eulerian

 Step1: Connectivity Check ( Check if all edges are present in 1 component only)
 Find a node with a degree > 0
 If no node found then Euler graph
 Else Do DFS and mark all nodes in component
 Check if any node with degree > 0 was unutilized
 If True then not a Euler Graph
 Step2: Count odd degree nodes (Use adjacency list)
 Count = 0 => Eulerian Graph
Don’t write or
 Count = 2 => Semi Eulerian Graph place any image
in this area
 Count > 0 => Not Eulerian Graph
Dr. D Khalandar Basha

Algorithms
 how do we find Eulerian or semi-eulerian graph
 Each algorithms will be described in terms of the input, steps to perform, and output
 Methods for finding an eulerian circuit
 Fleury’s Algorithm (easiest to walk through )
 Fleury’s Algorithm will produce either an eulerian circuit or an eulerian
trail depending on which solution is possible.
 Hierholzer’s Algorithm
 algorithm begins by finding an arbitrary circuit originating
Don’t write or
from the starting vertex. If this circuit contains all the edges of place any image
in this area
the graph, then an eulerian circuit has been found.
Dr. D Khalandar Basha

Fleury’s Algorithm
 Input: Connected graph G where zero or two vertices are odd.
 Steps:
 1. Choose a starting vertex, call it v.
 If G has no odd vertices, then any vertex can be the starting point.
 If G has exactly two odd vertices, then v must be one of the odd vertices.
 2. Choose an edge incident to v that is unlabeled and label it with the number in
which it was chosen, ensuring that the graph consisting of unlabeled edges remains
connected.
 3. Travel along the edge to its other endpoint. Don’t write or
place any image
 4. Repeat Steps (2) and (3) until all edges have been labeled. in this area

 Output: Labeled eulerian circuit or trail.

Dr. D Khalandar Basha

Fleury’s Algorithm
 The intention behind Fleury’s Algorithm is that you are prevented from getting stuck
at a vertex with no edges left to travel.
 In practice, it may be helpful to use two copies of the graph—one to keep track of the
route and the other where labeled edges are removed.
 This second copy makes it easier to see which edges are unavailable to be chosen.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Fleury’s Algorithm
 Example Input: A connected graph (shown below) where every vertex has even
degree. We are looking for an eulerian circuit.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Fleury’s Algorithm
 Step 1: Since no starting vertex is explicitly stated, choose vertex v as starting vertex.
 Step 2: We can choose any edge incident to v. Here we chose vx. The labeled graph is
on the left and the unlabeled portions are shown on the right with edges removed
that have already been chosen.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Fleury’s Algorithm
 Step 3: Looking at the graph to the right, we can choose any edge out of x.
Here we chose xy. The labeled and unlabeled graphs have been updated below.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Fleury’s Algorithm
 Step 4: At this point we cannot choose yv, as its removal would disconnect the
unlabeled graph shown on the right in Step 3. However, yx and yz are both valid
choices. Here we chose yx.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Fleury’s Algorithm
 Step 5: There is only one available edge xz.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Fleury’s Algorithm
 Step 6: There is only one available edge zy.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Fleury’s Algorithm
 Step 7: There is only one available edge yv.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Fleury’s Algorithm
 Step 8: Both vw and vu are valid choices for the next edge. Here we chose vw.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Fleury’s Algorithm
 Step 9: There is only one available edge wu.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Fleury’s Algorithm
 Step 10: There is only one available edge uv.

Don’t write or
 Output: The graph above on the left has an eulerian circuit labeled, place any image
in this area
starting and ending at vertex v.
Dr. D Khalandar Basha

Fleury’s Algorithm
 Does the graph below have an Euler Circuit? If so, find one.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Fleury’s Algorithm
 Does the graph below have an Euler Circuit? If so, find one.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Hamiltonian cycle

 When a graph would contain an eulerian circuit, that must travel through every
edge and vertex
 In graph theoretic terms, we are looking for a tour through the graph that hits
every vertex exactly once.
 What type of tour is this?
 If the start and end at the same location, we are searching for a cycle.
 If the starting and ending points can differ, we are searching for a path.
Dr. D Khalandar Basha

Hamiltonian cycle

 Definition :
 A cycle in a graph G that contains every vertex of G is called a hamiltonian cycle.
 A path that contains every vertex is called a hamiltonian path.
 A graph that contains a hamiltonian cycle is called hamiltonian.
 The Hamiltonian cycles and paths travel through every vertex exactly once.

 When comparing an eulerian circuit with a hamiltonian cycle, only one

requirement has been lifted: instead of a tour containing every edge and every
vertex, we are now only concerned with the vertices.
Dr. D Khalandar Basha

Hamiltonian cycle

 Definition :
 A cycle in a graph G that contains every vertex of G is called a hamiltonian cycle.
 A path that contains every vertex is called a hamiltonian path.
 A graph that contains a hamiltonian cycle is called hamiltonian.
 The Hamiltonian cycles and paths travel through every vertex exactly once.

 When comparing an eulerian circuit with a hamiltonian cycle, only one

requirement has been lifted: instead of a tour containing every edge and every
vertex, we are now only concerned with the vertices.
Dr. D Khalandar Basha

Hamiltonian cycle

 However, as often happens in mathematics,

when restrictions are relaxed,
the solution either does not exist or
finding a solution becomes more difficult.

 for eulerian circuits—

a graph simply needs to be connected with
all even vertices in order for an eulerian circuit to exist.
 The same is not true for hamiltonian cycles.
Dr. D Khalandar Basha

Hamiltonian cycle

 However, as often happens in mathematics,

when restrictions are relaxed,
the solution either does not exist or
finding a solution becomes more difficult.

 for eulerian circuits—

a graph simply needs to be connected with
all even vertices in order for an eulerian circuit to exist.
 The same is not true for hamiltonian cycles.
Dr. D Khalandar Basha

Hamiltonian cycle

 Example For each of the graphs below, determine if they have hamiltonian cycles
(and paths) and eulerian circuits (and trails).

 Since G is connected and all vertices are even,

 we know it has an eulerian circuit.
 There is no hamiltonian cycle since we need to
Include c in the cycle and by doing so we have
already passed through b twice,
making it impossible to visit a and d.
Dr. D Khalandar Basha

Hamiltonian cycle

 Example For each of the graphs below, determine if they have hamiltonian cycles
(and paths) and eulerian circuits (and trails).

 Since G is connected and all vertices are even, we know

 it is eulerian.
 Hamiltonian cycles and hamiltonian paths also exist.
 To find one such path, remove any one of edges from a
 hamiltonian cycle.
Dr. D Khalandar Basha

Hamiltonian cycle

 Example For each of the graphs below, determine if they have hamiltonian cycles
(and paths) and eulerian circuits (and trails).

 Since G is connected and all vertices are even, we know

 it is eulerian.
 Hamiltonian cycles and hamiltonian paths also exist.
 To find one such path, remove any one of edges from a
 hamiltonian cycle.
Dr. D Khalandar Basha

Hamiltonian cycle

 Example For each of the graphs below, determine if they have hamiltonian cycles
(and paths) and eulerian circuits (and trails).

 Some vertices of G are odd, so we know it is not eulerian.

 Moreover, since more than two vertices are odd,
 the graph is not semi-eulerian.
 However, this graph does have a hamiltonian cycle
(and so also a hamiltonian path).
Dr. D Khalandar Basha

Hamiltonian cycle

 Example For each of the graphs below, determine if they have hamiltonian cycles
(and paths) and eulerian circuits (and trails).

 Four vertices of G are odd, we know it is neither

eulerian nor semi-eulerian.
 This graph does not have a hamiltonian cycle since
 d cannot be a part of any cycle.
 Moreover, this graph does not have a hamiltonian
 path since any traversal of every vertex would need to travel
 through g multiple times.
Dr. D Khalandar Basha

Hamiltonian cycle

 If a graph has a hamiltonian cycle, it automatically has a hamiltonian path (just

leave off the last edge of the cycle to obtain a path).

 If a graph has a hamiltonian path, it may or may not have a hamiltonian cycle.
Dr. D Khalandar Basha

Hamiltonian cycle

Properties of Hamiltonian Graphs

 G must be connected.
 No vertex of G can have degree less than 2.
 G cannot contain a cut-vertex, i.e a vertex whose removal disconnects the graph.
 If G contains a vertex x of degree 2 then both edges incident to x must be included
in the cycle.
 If two edges incident to a vertex x must be included in the cycle, then all other
edges incident to x cannot be used in the cycle.
 If in the process of attempting to build a hamiltonian cycle, a cycle is formed that
does not span G, then G cannot be hamiltonian.
Dr. D Khalandar Basha

Hamiltonian cycle

 Example : Use the properties to show that the graphs are not hamiltonian.

 For G, notice that vertices a, b, e, and f all

have degree 2 and so all the edges incident
to these vertices must be included in the
cycle.
 But then edges cd and hg cannot be a part of
a cycle since they would create smaller cycles
that do not include all of the vertices in G.
Dr. D Khalandar Basha

Hamiltonian cycle
Dr. D Khalandar Basha

Dirac’s Theorem & Ore’s Theorem

Dirac’s Theorem
 Let G be a graph with n ≥ 3 vertices.
 If every vertex of G satisfies deg(v) ≥ n / 2, then G has a hamiltonian cycle.

Ore’s Theorem
 Let G be a graph with n ≥ 3 vertices.
 If deg(x) + deg(y) ≥ n for all distinct nonadjacent vertices, then G has a hamiltonian
cycle.
Don’t write or
place any image
in this area
Dr. D Khalandar Basha

The traveling salesman problem

 what if a graph is know to have a hamiltonian cycle?
 For example, every complete graph Kn (for n ≥ 3) must contain a hamiltonian
cycle since it satisfies the criteria of Dirac’s Theorem.

 A traveling salesman has customers in numerous cities; he must visit each of them
and return home, but wishes to do this with the least total cost; determine the
cheapest route possible for the salesman.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

the traveling salesman problem

 The graph that
models the general
Traveling Salesman
Problem (TSP) is
a weighted
complete
graph

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

the traveling salesman problem:

exhaustive search, or the Brute Force Algorithm
 To find the hamiltonian cycle of least total weight, one obvious method is to find all
possible hamiltonian cycles and pick the cycle with the smallest total.
 The method of trying every possibility to find an optimal solution is referred to as an
exhaustive search, or use of the Brute Force Algorithm.
 This method can be used for any number of problems, not just the Traveling Salesman
Problem, though the description below is only for finding hamiltonian cycles.
 Knowing this, you might be asking yourself why this problem is still being
studied.
Don’t write or
 If we have an algorithm that will find the optimal hamiltonian cycle, place any image
in this area
why are mathematicians still interested?
Dr. D Khalandar Basha

the traveling salesman problem:

exhaustive search, or the Brute Force Algorithm
 To find the hamiltonian cycle of least total weight, one obvious method is to find all
possible hamiltonian cycles and pick the cycle with the smallest total.
 The method of trying every possibility to find an optimal solution is referred to as an
exhaustive search, or use of the Brute Force Algorithm.
 This method can be used for any number of problems, not just the Traveling Salesman
Problem, though the description below is only for finding hamiltonian cycles.
 Knowing this, you might be asking yourself why this problem is still being
studied.
Don’t write or
 If we have an algorithm that will find the optimal hamiltonian cycle, place any image
in this area
why are mathematicians still interested?
Dr. D Khalandar Basha

Brute Force Algorithm

 Input: Weighted complete graph Kn.

 Steps:
 1. Choose a starting vertex, call it v.
 2. Find all hamiltonian cycles starting at v. Calculate the total weight of each cycle.
 3. Compare all (n−1)! cycles. Pick one with the least total weight. (Note: there
should be at least two options).

Don’t write or
 Output: Minimum hamiltonian cycle. place any image
in this area
Dr. D Khalandar Basha

Brute Force Algorithm

Example
 Sam is planning his next business trip
from his hometown of Addison and has
determined the cost for travel between
any of the five cities he must visit. This
information is modeled in the weighted
complete graph on the next page, where
the weight is given in terms of dollars. Use
Don’t write or
Brute Force to find all possible routes for place any image
in this area
his trip.
Dr. D Khalandar Basha

Brute Force Algorithm

 One method for finding all hamiltonian cycles, and ensuring you indeed have all 24, is
to use alphabetical or lexicographic ordering of the cycles.
 Note that all cycles must start and end at Addison and we will abbreviate all cities
with their first letter.
 For example, the first cycle is a b c d e a and appears first in the list below.
 Below each cycle is its reversal and total weight.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Brute Force Algorithm

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Brute Force Algorithm

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Brute Force Algorithm

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Brute Force Algorithm

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Brute Force Algorithm

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Brute Force Algorithm

From the data above we can identify the optimal cycle as a c b e d a,

which provides Sam with the optimal route of Addison to Chelsea to Don’t write or
Bristol to Essex to Dover and back to Addison, for a total at a cost of place any image
in this area
$1270.
Dr. D Khalandar Basha

Brute Force Algorithm

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Brute Force Algorithm

 approximate algorithms, which are efficient but not optimal.
 This means they can find a good hamiltonian cycle without taking too much
computational time.
 In some instances these algorithms may in fact find the optimal cycle, but there is no
guarantee that this will always occur.
 Nearest Neighbor Algorithm.
 Repetitive Nearest Neighbor Algorithm
 Cheapest Link
Don’t write or
 Nearest Insertion place any image
in this area
Dr. D Khalandar Basha

Nearest Neighbor Algorithm

 Input: Weighted complete graph Kn.
 Steps: 1. Choose a starting vertex, call it v. Highlight v.
 2. Among all edges incident to v, pick the one with the smallest weight.
 If two possible choices have the same weight, you may randomly pick one.
 3. Highlight the edge and move to its other endpoint u. Highlight u.
 4. Repeat Steps (2) and (3), where only edges to unhighlighted vertices are
considered.
 5. Close the cycle by adding the edge to v from the last vertex highlighted. Calculate
Don’t write or
the total weight. place any image
in this area
 Output: hamiltonian cycle.
Dr. D Khalandar Basha

Nearest Neighbor Algorithm

 Input: Weighted complete graph Kn.
 Steps: 1. Choose a starting vertex, call it v. Highlight v.
 2. Among all edges incident to v, pick the one with the smallest weight.
 If two possible choices have the same weight, you may randomly pick one.
 3. Highlight the edge and move to its other endpoint u. Highlight u.
 4. Repeat Steps (2) and (3), where only edges to unhighlighted vertices are
considered.
 5. Close the cycle by adding the edge to v from the last vertex highlighted.
Don’t write or
 Calculate the total weight. place any image
in this area
 Output: hamiltonian cycle.
Dr. D Khalandar Basha

Nearest Neighbor Algorithm

 At each step we will show two copies of the graph.
 One is edges under consideration and the other traces the route under construction.
 Step 1: The starting vertex is a.
 Step 2: The edge of smallest weight incident to a is ae with weight 100.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Nearest Neighbor Algorithm

 Step 3: From e we only consider edges to b, c, or d. Choose edge eb with weight 225.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Nearest Neighbor Algorithm

 Step 4: From b we consider the edges to c or d. The edge of smallest weight is bc with
weight 315.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Nearest Neighbor Algorithm

 Step 5: Even though cd does not have the smallest weight among all edges
 incident to c, it is the only choice available.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Nearest Neighbor Algorithm

 Step 6: Close the circuit by adding da.

Don’t write or
 Output: The circuit is a e b c d a with total weight 1365 place any image
in this area
Dr. D Khalandar Basha

Nearest Neighbor Algorithm

 In the Brute Force algorithm, the final circuit was Addison to Essex to Bristol
to Chelsea to Dover and back to Addison.
 Although Nearest Neighbor did not find the optimal circuit of total cost $1270, it did
produce a fairly good circuit with total cost $1365.
 The speed with which Nearest Neighbor found this circuit.
 By using a different starting vertex, the Nearest Neighbor Algorithm may identify a
new hamiltonian cycle, which may be better or worse than the initial cycle.
 Instead of only considering the circuits starting at the chosen vertex we
Don’t write or
will run Nearest Neighbor with each of the vertices as a starting point. place any image
in this area
 This is called Repetitive Nearest Neighbor.
Dr. D Khalandar Basha

Repetitive Nearest Neighbor Algorithm

 Input: Weighted complete graph Kn.

 Steps:
 1. Choose a starting vertex, call it v.
 2. Apply the Nearest Neighbor Algorithm.
 3. Repeat Steps (1) and (2) so each vertex of Kn serves as the starting vertex.
 4. Choose the cycle of least total weight. Rewrite it with the desired reference point.

Don’t write or
 Output: hamiltonian cycle. place any image
in this area
Dr. D Khalandar Basha

Repetitive Nearest Neighbor Algorithm

 The five cycles are shown below, with the original name, the rewritten form with a as
the reference point, and the total weight of the cycle.
 The cycle starting at d is the same as the one starting at a, and the cycle starting at b is
their reversal.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Repetitive Nearest Neighbor Algorithm

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Repetitive Nearest Neighbor Algorithm

 It should come as no surprise that Repetitive Nearest Neighbor performs better than
Nearest Neighbor; however, there is no guarantee that this improvement will produce
the optimal cycle.
 This small increase in cost would clearly be worth the time savings over Brute Force.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Cheapest Link Algorithm

 Even though Repetitive Nearest Neighbor addressed the concern of missing
small weight edges, it is still possible that some of these will be bypassed as
we travel a cycle.
 The Cheapest Link Algorithm attempts to fix this by choosing edges in order of weight
as opposed to edges along a tour.
 Unlike either version of Nearest Neighbor, Cheapest Link does not follow a path that
eventually closes into a cycle, but rather chooses edges by weight in such a
way that they eventually form a cycle.
Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Cheapest Link Algorithm

 Input: Weighted complete graph Kn.
 Steps:
 1. Among all edges in the graph pick the one with the smallest weight. If two
possible choices have the same weight, you may randomly pick one. Highlight the
edge.
 2. Repeat Step (1) with the added conditions:
 (a) no vertex has three highlighted edges incident to it; and
 (b) no edge is chosen so that a cycle closes before hitting all the vertices.
Don’t write or
 3. Calculate the total weight. place any image
in this area
 Output: hamiltonian cycle.
Dr. D Khalandar Basha

Cheapest Link Algorithm

Example
 Solution: In each step shown, unchosen
edges are shown in gray, previously
chosen edges are in black, and the newly
chosen edge in bold.
 An edge that is skipped will be marked
with an X.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Cheapest Link Algorithm

 Step 1: The smallest weight is 100 for edge ae.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Cheapest Link Algorithm

 Step 2: The next smallest weight is 125 with edge ad

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Cheapest Link Algorithm

 Step 3: The next smallest weight is 225 for edge be

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Cheapest Link Algorithm

 Step 4: Even though ac has weight 300, we must bypass it as it would force a to have
three incident edges that are highlighted.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Cheapest Link Algorithm

 Step 5: The next smallest weight is 305 for edge ed, but again we must bypass it as it
would close a cycle too early as well as force e to have three incident edges that are
highlighted.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Cheapest Link Algorithm

 Step 6: The next available is bc with weight 315.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Cheapest Link Algorithm

 Step 6: The next available is bc with weight 315.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Cheapest Link Algorithm

 Step 7: At this point, we must close the cycle with the only one choice of cd.

Don’t write or
place any image
in this area
 Output: The resulting cycle is a e b c d a with total weight 1365.
Dr. D Khalandar Basha

Relative error
 The relative error for a solution is given by

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Relative error
 The relative error for a solution is given by

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Shortest path
 The shortest way to travel between two locations is perhaps one of the oldest
questions.
 This problem can be described in graph theoretic terms as the search for a shortest
path on a weighted graph.
 Recall that a path is a sequence of vertices in which there is an edge between
consecutive vertices and no vertex is repeated.
 As with the algorithms for the Traveling Salesman Problem, the weight associated to
an edge may represent more than just distance (e.g., cost or time) and the
Don’t write or
shortest path really indicates the path of least total weight. place any image
in this area
Dr. D Khalandar Basha

Dijkstra Algorithm
 In 1956 Edsger W. Dijkstra proposed the algorithm to study not out of necessity for
finding a shortest route, but rather as a demonstration of the power of a new
“automatic computer” at the Mathematical Centre in Amsterdam.
 This algorithm would become in almost every GIS (Geographic Information System,
or mapping software) uses a modification of Dijkstra’s Algorithm to
provide directions.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Dijkstra Algorithm
 Numerous versions of Dijkstra’s Algorithm exist, though two basic descriptions
 In one, a shortest path from starting and ending vertex is found.
 we will study the more general version that finds the shortest path from a specific
vertex to all other vertices in the graph.
 Dijkstra’s Algorithm is a bit more complex than the algorithms.
 Each vertex is given a two-part label L(v) = (x,(w(v)).
 The first portion of the label is the name of the vertex used to travel to v.
 The second part is the weight of the path that was used to get to v from
Don’t write or
the designated starting vertex. place any image
in this area
Dr. D Khalandar Basha

Dijkstra Algorithm
 At each stage of the algorithm, consider a set of free vertices, denoted by an F below.
Free vertices are the neighbors of previously visited vertices that are themselves
not yet visited.
 The most complex portion of this algorithm is the labeling of the vertices and how
they are updated with iterations of Step.
 In the initial step of Dijkstra’s Algorithm, all vertices have no entry in the first part
of the label and the second part is 0 for the starting vertex and ∞ for all others.
 Note that the set F of free vertices consists of all neighbors of highlighted
Don’t write or
vertices and all are under consideration for becoming the next highlighted place any image
in this area
vertex.
Dr. D Khalandar Basha

Dijkstra Algorithm
 Input: Weighted connected simple graph G = (V, E, w) and designated Start vertex.
 Steps:
 1. For each vertex x of G, assign a label L(x) so that L(x) = (−, 0) if x = Start and L(x) =
(−, ∞) otherwise. Highlight Start.
 2. Let u = Start and define F to be the neighbors of u. Update the labels for each
vertex v in F as follows:
 if w(u) + w(uv) < w(v), then redefine L(v) = (u, w(u) + w(uv)) otherwise do not
change L(v)
Don’t write or
 3. Highlight the vertex with lowest weight as well as the edge uv used to place any image
in this area
update the label. Redefine u = v.
Dr. D Khalandar Basha

Dijkstra Algorithm
 4. Repeat Steps (2) and (3) until each vertex has been reached. In all future
iterations, F consists of the un-highlighted neighbors of all previously highlighted
vertices and the labels are updated only for those vertices that are adjacent to the
last vertex that was highlighted.
 5. The shortest path from Start to any other vertex is found by tracing back using
the first component of the labels. The total weight of the path is the weight
given in the second component of the ending vertex.

Don’t write or
 Output: Highlighted path from Start to any vertex x of weight w(x). place any image
in this area
Dr. D Khalandar Basha

Dijkstra Algorithm
 Example Apply Dijkstra’s Algorithm to the graph below where Start = g.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Dijkstra Algorithm
 Step 1: Highlight g. Define L(g) = (−, 0) and L(x) = (−, ∞) for all x = a, · · · , f.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Dijkstra Algorithm
 Step 2: Let u = g. Then the neighbors of g comprise F = {a, f}. We
 Compute w(g) + w(ga) = 0 + 9 = 9 < ∞ = w(a)
w(g) + w(gf) = 0 + 1 = 1 < ∞ = w(f)
 Update L(a) = (g, 9) and L(f) = (g, 1). Since the minimum weight for all vertices in F
is that of f, we highlight the edge gf and the vertex f.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Dijkstra Algorithm
 Step 3: Let u = f.
 Then the neighbors of all highlighted vertices are F = {a, b, d, e}. We compute
 w(f) + w(f a) = 1 + 1 = 2 < 9 = w(a)
 w(f) + w(f b) = 1 + 2 = 3 < ∞ = w(b)
 w(f) + w(f d) = 1 + 1 = 2 < ∞ = w(d)
 w(f) + w(fe) = 1 + 8 = 9 < ∞ = w(e)
 Update L(a) = (f, 2), L(b) = (f, 3),
L(d) = (f, 2) and L(e) = (f, 9).
Don’t write or
 Since the minimum weight for all vertices in F is that of a or d, we choose place any image
in this area
to highlight the edge f a and the vertex a.
Dr. D Khalandar Basha

Dijkstra Algorithm

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Dijkstra Algorithm
 Step 4: Let u = a.
 Then the neighbors of all highlighted vertices are
F = {b, d, e}.
 Note, updating the label for b since this is the only
vertex adjacent to a, the vertex highlighted in the
previous step.
 w(a) + w(ba) = 2 + 6 = 8 ≮ 3 = w(b)
 Do not update the label for b since the computation above is not less
Don’t write or
than the current weight of b. place any image
in this area
Dr. D Khalandar Basha

Dijkstra Algorithm
 The minimum weight for all vertices in F is that of d, and so we highlight the edge f d
and the vertex d

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Dijkstra Algorithm
 Step 5: Let u = d.
 Then the neighbors of all highlighted vertices are
F = {b, c, e}. We compute
 w(d) + w(dc) = 2 + 5 = 7 < ∞ = w(c)
 w(d) + w(de) = 2 + 6 = 8 < 9 = w(e)
 Update L(c) = (d, 7) and L(e) = (d, 8).
 Since the minimum weight for all vertices in F is that of b, we highlight the edge bf
and the vertex b.
Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Dijkstra Algorithm

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Dijkstra Algorithm
 Step 6: Let u = b. Then the neighbors of all highlighted vertices are F = {c, e}.
However, we only consider updating the
label of c since e is not adjacent to b.
 Since w(b) + w(bc) = 3 + 5 = 8 ≮ 7 = w(c)
 we do not update the labels of any vertices.
 Since the minimum weight for all vertices in
 F is that of c we highlight the edge dc and the
 Vertex c.
Don’t write or
 This terminates the iterations of the algorithm since our ending vertex place any image
in this area
 has been reached.
Dr. D Khalandar Basha

Dijkstra Algorithm

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Dijkstra Algorithm
 Step 7: Let u = c.
 Then the neighbors of all highlighted vertices
are F = {e}.
 However, we do not need to update any labels
since c and e are not adjacent.
 Thus we highlight the edge de and the vertex e.
 This terminates the iterations of the algorithm since all vertices are now
highlighted.
Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Dijkstra Algorithm

 Output: The shortest paths from g to all other vertices can be found
highlighted above. For example the shortest path from g to c is g f d c Don’t write or
place any image
and has a total weight 7, as shown by the label of c. in this area
Dr. D Khalandar Basha

Walks using Matrices

 How to model a graph using an adjacency matrix.
 Another use for the adjacency matrix is to count the number of walks between two
vertices within a graph.
 Consider the graph shown below with its adjacency matrix A on the right.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Walks using Matrices

 If we want a walk of length 1. So to count the number of walks of length 1 from v1 to
v3, we need only to count the number of edges (namely 2) between these vertices.
 If we want the walks of length 2?
 By inspection, we can see there is only one, which is

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

Walks using Matrices

 How could we count this? If we know how many walks there are from v1 to
 v2 (1) and then the number from v2 to itself (1), we can get one type of walk
 from v1 to v2. Also, we could count the number of walks from v1 to v3 (2) and
 then the number of walks from v3 to v2 (1). In total we have 1 ∗ 1 + 2 ∗ 1 = 3
 walks from v1 to v2. Note that we did not include any walks of the form v1v1v2
 since there are no edges from v1 to itself.
 Viewing this as a multiplication of vectors, we have

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

ESSENTIALS OF PROBLEM SOLVING

Don’t write or place any

image in this area
Dr. D Khalandar Basha

Fleury’s Algorithm
 Does the graph below have an Euler Circuit? If so, find one.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

DEPTH FIRST SEARCH ( DFS ) ALGORITHM

 Key points
 DFS is an algorithm for traversing a Graph or a Tree.
 DFS starts with the root node and explores all the nodes along the depth of the
selected path before backtracking to explore the next path.
 DFS makes use of Stack for storing the visited nodes of the graph / tree.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

DEPTH FIRST SEARCH ( DFS ) ALGORITHM

 Example: Consider the below step-by-step DFS traversal of the tree. If the source is
root ( node 0 ), the nodes 2 & 4 along the depth of the tree are explored before the
other nodes in the tree.

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

DEPTH FIRST SEARCH ( DFS ) ALGORITHM

 Step 1: Start with the root (source), mark it as visited and push it in the Stack

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

DEPTH FIRST SEARCH ( DFS ) ALGORITHM

 Step 2: While the stack is not empty. Do the below

 A) Remove the node at the top of the stack i.e. Node 0
 B) Add Node 0 to DFS traversal order
 C) Push the nodes adjacent to Node 0 that have not been visited, into the Stack (1, 2)

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

DEPTH FIRST SEARCH ( DFS ) ALGORITHM

 Step 3: While the stack is not empty. Do the below

 A) Remove the node at the top of the stack i.e. Node 2
 B) Add Node 2 to DFS traversal order
 C) Push the nodes adjacent to Node 2 that have not been visited, into the Stack (5)

Don’t write or
place any image
in this area
Dr. D Khalandar Basha

DEPTH FIRST SEARCH ( DFS ) ALGORITHM

 Step 4: While the stack is not empty. Do the below

 A) Remove the node at the top of the stack i.e. Node 5
 B) Add Node 5 to DFS traversal order
 C) Push the nodes adjacent to Node 5 that have not been visited, into the Stack

Note: The adj to Node 5 is Node 2

which has already been visited
Dr. D Khalandar Basha

DEPTH FIRST SEARCH ( DFS ) ALGORITHM

 Step 5: While the stack is not empty. Do the below

 A) Remove the node at the top of the stack i.e. Node 1
 B) Add Node 1 to DFS traversal order
 C) Push the nodes adjacent to Node 1 that have not been visited, into the Stack (3, 4)
Dr. D Khalandar Basha

DEPTH FIRST SEARCH ( DFS ) ALGORITHM

 Step 6: While the stack is not empty. Do the below

 A) Remove the node at the top of the stack i.e. Node 4
 B) Add Node 4 to DFS traversal order
 C) Push the nodes adjacent to Node 4 that have not been visited, into the Stack

Note: as the only adj to Node 4

is 1 that has alreasy been visited
Dr. D Khalandar Basha

DEPTH FIRST SEARCH ( DFS ) ALGORITHM

 Step 7: While the stack is not empty. Do the below

 A) Remove the node at the top of the stack i.e. Node 3
 B) Add Node 3 to DFS traversal order
 C) Push the nodes adjacent to Node 3 that have not been visited, into the Stack

Note: as the only adj to Node 3

is 1 that has alreasy been visited
Dr. D Khalandar Basha

DEPTH FIRST SEARCH ( DFS ) ALGORITHM

Algorithm : Depth first search (Graph G, Souce_Vertex S)

1. Create a stack STK to store the vertices.
2. Push the source vertex S in the stack STK.
3. While the stack STK is not empty
4. Pop the vertex U from the top of the stack. i.e Vertex U = [Link](), [Link]()
5. If the vertex U is not visited, Then
6. Explore the vertex U and mark U as visited.
7. For every vertex V adjacent to vertex U
8. Push the vertex V in the stack STK
Dr. D Khalandar Basha

DEPTH FIRST SEARCH ( DFS ) ALGORITHM

Example of depth-first search traversal on a graph : In the below unweighted graph,

the DFS algorithm beings by exploring node ‘0’, followed by its adjacent vertex node
‘1’, followed by its adjacent vertex node ‘3’ and so on.
Dr. D Khalandar Basha

DEPTH FIRST SEARCH ( DFS ) ALGORITHM

Dr. D Khalandar Basha

DEPTH FIRST SEARCH ( DFS ) ALGORITHM

Dr. D Khalandar Basha

DEPTH FIRST SEARCH ( DFS ) ALGORITHM

Dr. D Khalandar Basha

DEPTH FIRST SEARCH ( DFS ) ALGORITHM

Dr. D Khalandar Basha

DEPTH FIRST SEARCH ( DFS ) ALGORITHM

 Data structure used for storing graph or tree : Adjacency List

 Data structure used for depth first search : Stack
 Time complexity of depth first search : O ( V + E ) for an adjacency list
implementation of a graph or a tree.
 ‘V’ is the number of vertices and ‘E’ is the number of edges in a graph/tree.
.
Dr. D Khalandar Basha

DEPTH FIRST SEARCH ( DFS ) ALGORITHM

Why is the time complexity of depth first search algorithm O ( V + E ) :

 When the graph is stored in an adjacency list, the neighbors of a vertex on the out
going edge are explored successively/linearly.
 As each vertex is explored only once, all the vertices are explored in O ( V ) time.
 The total number of edges (maintained in the adjacency list) are 2*E (bi-
directional) for an undirected graph and E for a directed graph.
 Thus the time complexity is
 O ( 2.E + V ) for an undirected graph and
 O ( E + V ) for a directed graph.
Dr. D Khalandar Basha

BREADTH FIRST SEARCH ( BFS ) ALGORITHM

Key points
 Breadth First Search (BFS) is an algorithm for traversing an unweighted Graph or a
Tree.
 BFS starts with the root node and explores each adjacent node before exploring
node(s) at the next level.
 BFS makes use of Queue for storing the visited nodes of the graph / tree.
Dr. D Khalandar Basha

BREADTH FIRST SEARCH ( BFS ) ALGORITHM

Example : Consider the below step-by-step BFS traversal of the tree. If the source is
root ( node 0 ), the immediately connected nodes 1 & 2 are considered at the same
level and are explored before the other nodes in the tree
Dr. D Khalandar Basha

BREADTH FIRST SEARCH ( BFS ) ALGORITHM

Dr. D Khalandar Basha

BREADTH FIRST SEARCH ( BFS ) ALGORITHM

Dr. D Khalandar Basha

BREADTH FIRST SEARCH ( BFS ) ALGORITHM

Dr. D Khalandar Basha

BREADTH FIRST SEARCH ( BFS ) ALGORITHM

Dr. D Khalandar Basha

BREADTH FIRST SEARCH ( BFS ) ALGORITHM

Dr. D Khalandar Basha

BREADTH FIRST SEARCH ( BFS ) ALGORITHM

Dr. D Khalandar Basha

BREADTH FIRST SEARCH ( BFS ) ALGORITHM

Dr. D Khalandar Basha

BREADTH FIRST SEARCH ( BFS ) ALGORITHM

Dr. D Khalandar Basha

Walk

[Link]

[Link]

[Link]

[Link]
[Link]
[Link]
[Link]
[Link] 1023/topics/Topic-20211/subtopics/Subtopic-266111/
[Link]
Don’t write or
[Link]
place any image
tions%3A_An_Introduction_to_Topics_in_Discrete_Mathematics_(Sylvestre)/15%3A_Paths_and_connect
in this area
edness/15.02%3A_Walks_trails_and_paths
Dr. D Khalandar Basha

Stack and Queue

 Data structure organizes the storage in computers so that we can easily access and
change data.
 Stacks and Queues are the earliest data structure defined in computer science.
 A simple Python list can act as a queue and stack as well.
 A queue follows FIFO rule (First In First Out) and used in programming for sorting.
 It is common for stacks and queues to be implemented with an array or linked list.
Dr. D Khalandar Basha

Stack and Queue

 A Stack is a data structure that follows the LIFO(Last In First Out) principle.
Dr. D Khalandar Basha

Stack and Queue

 To implement a stack, we need two simple operations:

 push - It adds an element to the top of the stack.
 pop - It removes an element from the top of the stack.
Dr. D Khalandar Basha

Stack and Queue

 stack = []

 # append() function to push # element in the stack

 [Link]('a')
 [Link]('b')
 [Link]('c')
 print('Initial stack‘, stack)
Dr. D Khalandar Basha

Stack and Queue

 # pop() function to pop -- element from stack in

 # LIFO order
 print('\nElements popped from stack:')
 print([Link]())
 print([Link]())
 print([Link]())

 print('\nStack after elements are popped:')

 print(stack)
Dr. D Khalandar Basha

Stack and Queue

 A Queue follows the First-in-First-Out (FIFO) principle. It is opened from both the
ends hence we can easily add elements to the back and can remove elements from
the front.
 To implement a queue, we need two simple operations:
 enqueue - It adds an element to the end of the queue.
 dequeue - It removes the element from the beginning of the queue.
Dr. D Khalandar Basha

Stack and Queue

Dr. D Khalandar Basha

Stack and Queue