Graph Theory: Best Answers 007EH

Welcome to Lesson Ten – Graph Theory.

You can also join the Discrete Mathematics Forum to interact and share ideas, also you can navigate to any session using the Table of Content

Don’t forget to leave your comment, suggestions regarding the previous, and current lecture to help us improve.

Introduction to Graph Theory

Graph:

Graph G consists of two things:

1. A set V=V(G) whose elements are called vertices, points or nodes of G.

2. A set E = E(G) of an unordered pair of distinct vertices called edges of G.

3. We denote such a graph by G(V, E) vertices u and v are said to be adjacent if there is an edge e ={u, v}.

Graph

4. In such a case u and v are called the endpoint of e={u, v} and e are said to connect u and v.

Degree of a Vertex:

The degree of a vertex is the number of edges incident on a vertex v. The self-loop is counted twice. The degree of a vertex is denoted by d(v).

Example1: Consider the graph G shown in fig. Determine the degree of each vertex.

Graph

Solution: The degree of each vertex is as follows:

                  d(a)=3;       d(b)=5;       d(c) = 2;       d(d)=2.

Example2: Verify that the sum of the degrees of all the vertices is even for the graph shown in fig:

Graph

Solution: The sum of the degrees of all the vertices is:

                  =d (v1)+d(v2 )+d(v3 )+d(v4 )+d(v5 )+d(v6 )+d(v7 )+d(v8)
                  = 2+3+3+3+3+4+2+2=22, which is even.

Example3: Verify that there are even numbers of vertices of odd degrees in the graph shown in fig:

Graph

Solution: The number of vertices of degree odd is 8, and each has a degree three in the above graph. Hence, we have even number of vertices of odd degrees.

Path:

A path of length n is a sequence of n+1 vertices of a graph in which each pair of vertices is an edge of the graph.

  1. A Simple Path: The path is called simple one if no edge is repeated in the path, i.e., all the vertices are distinct except that first vertex equal to the last vertex.
  2. An Elementary Path: The path is called elementary one if no vertex is repeated in the path, i.e., all the vertices are distinct.
  3. Circuit or Closed Path: The circuit or closed path is a path in which starts and ends at the same vertex, i.e., v0=vn.
  4. Simple Circuit Path: The simple circuit is a simple path which is a circuit.

Example: Consider the graph shown in fig: Give an example of the following:

  1. A simple path fromV1 to V6.
  2. An elementary path from V1 to V6.
  3. A simple path which is not elementary from V1 to V6.
  4. A path which is not simple and starting fromV2.
  5. A simple circuit starting from V1
  6. A circuit which is not simple and starting from V2.
Graph

Solution:

  1. A simple path fromV1 to V6.
            V1,V2,V3,V4,V5,V6.
  2. An elementary path from V1 to V6.
            V1,V2,V3,V5,V4,V6.
  3. A simple path which is not elementary from V1 to V6.
            V1,V2,V3,V5,V2,V4,V6.
  4. A path which is not simple and starting fromV2.
            V2,V3,V4,V5,V3,V4,V6.
  5. A simple circuit starting fromV1.
            V1,V2,V4,V6,V5,V3,V1
  6. A circuit which is not simple and starting from V2.
            V2,V3,V1,V2,V5,V4,V2.

Pendant Vertex: A vertex with degree one is called a Pendant Vertex.

Pendant Edge: The only edge which is an incident with a pendant vertex is called the Pendant Edge.

Odd Vertex: A vertex having degree odd is called an odd vertex.

Even Vertex: A vertex having a degree even is called an even vertex.

Incident Edge: An edge is called incident with the vertices is connects.

Adjacent Vertices: Two vertices are called adjacent if an edge links them. If there is an edge (u, v), then we can say vertex u is adjacent to vertex v, and vertex v is adjacent to vertex u.

Example: Consider the graph as shown in fig:

Graph

Determine the following:

  1. Pendant Vertices
  2. Pendant Edges
  3. Odd vertices
  4. Even Vertices
  5. Incident Edges
  6. Adjacent Vertices

Solution:

  1. The vertex V5is the pendant vertex.
  2. The edge (V4,V5) or e5 is the pendant edge.
  3. The vertices V3 and V5 are odd vertices.
  4. The vertices V1, V2,and V4 are even vertices.
  5. The edge e1 is an incident on V1, and V2.
        The edge e2 is an incident on V1 and V3.
        The edge e3 is an incident on V2 and V3.
        The edge e4 is an incident on V3 and V4.
        The edge e5 is an incident on V4 and V5.
  6. The vertex V1 is adjacent to V2 and V3.
        The vertex V2 is adjacent to V1 and V2.
        The vertex V3 is adjacent to V1 and V4
        The vertex V4 is adjacent to V3 and V5
        The vertex V5 is adjacent to V4.

Self-Loop: A self-loop is an edge e if it has the same endpoint.

The graph shown in fig contains the self-loop at vertex b,i.e., e=(b, b).

Isolated Vertex: A vertex with degree 0 is called Isolated Vertex.

Graph

Cut Set: Consider a graph G=(V, E).A cut set for G is the smallest set of edges such that the removal of the set, disconnected the graph whereas the removal of any proper subset of this set left a connected subgraph.

Example: Consider the graph shown in fig. Determine the cut set for this group.

Graph

Solution: For this graph, the edge set {(V1,V5),(V7,V5)} is a cut set. After the removal of the set, we have left with a disconnected subgraph. While after the removal of any of its proper subset, we have left with a connected subgraph.

Cut Points or Cut Vertices: Consider a graph G=(V, E). A cut point for a graph G is a vertex v such that G-v has more connected components than G or disconnected.

The subgraph G-v is obtained by deleting the vertex v from graph G and also deleting the entire edges incident on v.

Example: Consider the graph shown in fig. Determine the subgraphs

(i)G-v1     (ii) G-v3     (iii) G-v5

Graph

Solution:

  1. The subgraph G-v1 is shown in fig
  2. The subgraph G-v3 is shown in fig
  3. The subgraph G-v5 is shown in fig
Graph

Bridge (Cut Edges): Consider a graph G=(V, E).A bridge for a graph G, is an edge e such that G-e has more connected components than G or disconnected.

Example: Consider the graph shown in fig. Determine the subgraphs

(i)G-e1     (ii) G-e3     (iii) G-e4

Graph

Solution:

  1. The subgraph G-e1 is shown in fig
  2. The subgraph G-e3 is shown in fig
  3. The subgraph G-e4 is shown in fig
Graph
Graph


Types of Graphs:

1. Null Graph: A null graph is defined as a graph which consists only the isolated vertices.

Example: The graph shown in fig is a null graph, and the vertices are isolated vertices.

Types of Graphs

2. Undirected Graphs: An Undirected graph G consists of a set of vertices, V and a set of edge E. The edge set contains the unordered pair of vertices. If (u, v)∈E then we say u and v are connected by an edge where u and v are vertices in the set V.

Example: Let V = {1, 2, 3, 4} and E = {(1, 2), (1, 4), (3, 4), (2, 3)}.Draw the graph.

Solution: The graph can be drawn in several ways.

Two of which are as follows:

Types of Graphs

3. Multigraph: If in a graph multiple edges between the same set of vertices are allowed, it is known as Multigraph. In other words, it is a graph having at least one loop or multiple edges.

Types of Graphs

4. Directed Graphs: A directed graph or digraph G is defined as an unordered pair (V, E), where V is the set of points called vertices and E is the set of edges. Each edge in the graph G is assigned a direction and is identified with an ordered pair (u, v), where u is the initial vertex, and v is the end vertex.

Example: Consider the graph G = (V, E) as shown in fig. Determine the vertex set and edge set of graph G.

Types of Graphs

Solution: The vertex and edge set of graph G =(V, E) is as follow                G={{1,2,3},{(1,2),(2,1),(2,2),(2,3),(1,3)}}.

5. Undirected Complete Graph: An undirected complete graph G=(V,E) of n vertices is a graph in which each vertex is connected to every other vertex i.e., and edge exist between every pair of distinct vertices. It is denoted by Kn.A complete graph with n vertices will have Types of Graphs edges.

Example: Draw Undirected Complete Graphs k4and k6.

Solution: The undirected complete graph of k4 is shown in fig1 and that of k6is shown in fig2.

Types of Graphs

6. Connected and Disconnected Graph:

Connected Graph: A graph is called connected if there is a path from any vertex u to v or vice-versa.

Disconnected Graph: A graph is called disconnected if there is no path between any two of its vertices.

Example: Consider the graph shown in fig. Determine whether the graphs are

(a)Disconnected Graph

(b)Connected Graph.

Also, write their connected components.

Types of Graphs

Solution:

(i) The graph is shown in fig is a Disconnected Graph, and its connected components are

            {V1,V2,V3,V4},{V5,V6,V7,V8} and {V9,V10}.

(ii) The graph shown in fig is a Disconnected Graph and its connected components are

            {V1,V2},{V3,V4},{V5,V6},{V7,V8},{V9,V10}and {V11,V12}.

Types of Graphs

(iii) The graph shown in fig is a connected graph.

Types of Graphs

7. Connected Component: A subgraph of graph G is called the connected component of G, if it is not contained in any bigger subgraph of G, which is connected. It is defined by listing its vertices.

Example: Consider the graph shown in fig. Determine its connected components.

Types of Graphs

Solution: The connected components of this graph is {a, b, c}, {d, e, f}, {g, h ,i} and {j}.

8. Directed Complete Graph: A directed complete graph G = (V, E) on n vertices is a graph in which each vertex is connected to every other vertex by an arrow. It is denoted by Kn.

Example: Draw directed complete graphs K3 and K5.

Solution: Place the number of vertices at the appropriate place and then draw an arrow from each vertex to every other vertex as shown in fig:

Types of Graphs
Types of Graphs

9. Complementary Graph: The complement of a graph G is defined to be a graph which has the same number of vertices as in graph G and has two vertices connected if and only they are not related in the graph.

Example: Consider the graph G shown in fig. Find the complement of this graph.

Types of Graphs

Solution: The complement of the above graph is shown in Fig:

Types of Graphs

10. Labeled Graphs: A graph G=(V, E) is called a labeled graph if its edges are labeled with some name or data. So, we can write these labels in place of an ordered pair in its edges set.

Example: The graph shown in fig is labeled graphs.

            G= {{a, b, c, d}, {e1,e2,e3,e4}}

Types of Graphs

11.Weighted Graphs: A graph G=(V, E) is called a weighted graph if each edge of graph G is assigned a positive number w called the weight of the edge e.

Example: The graph shown in fig is a Weighted Graph.

Types of Graphs


Representation of Graphs

There are two principal ways to represent a graph G with the matrix, i.e., adjacency matrix and incidence matrix representation.

(a)Representation of the Undirected Graph:

1. Adjacency Matrix Representation: If an Undirected Graph G consists of n vertices then the adjacency matrix of a graph is an n x n matrix A = [aij] and defined by

Representation of Graphs

If there exists an edge between vertex vi and vj, where i is a row and j is a column then the value of aij=1.

If there is no edge between vertex vi and vj, then value of aij=0.

Example: Find the adjacency matrix MA of graph G shown in Fig:

Representation of Graphs

Solution: Since graph G consist of four vertices. Therefore, the adjacency matrix wills a 4 x 4 matrix. The adjacency matrix is as follows in fig:

Representation of Graphs

2. Incidence Matrix Representation: If an Undirected Graph G consists of n vertices and m edges, then the incidence matrix is an n x m matrix C = [cij] and defined by

Representation of Graphs

There is a row for every vertex and a column for every edge in the incident matrix.

The number of ones in an incidence matrix of the undirected graph (without loops) is equal to the sum of the degrees of all the vertices in a graph.

Example: Consider the undirected graph G as shown in fig. Find its incidence matrix MI.

Representation of Graphs

Solution: The undirected graph consists of four vertices and five edges. Therefore, the incidence matrix is an 4 x 5 matrix, which is shown in Fig:

Representation of Graphs

(b)Representation of Directed Graph:

1. Adjacency Matrix Representation: If a directed graph G consists of n vertices then the adjacency matrix of a graph is an n x n matrix A = [aij] and defined by

Representation of Graphs

If there exists an edge between vertex Vi and Vj, with Vi as initial vertex and Vj as a final vertex, then the value of aij=1.

If there is no edge between vertex Vi and Vj, then the value of aij=0.

The number of ones in the adjacency matrix of a directed graph is equal to the number of edges.

Example: Consider the directed graph shown in fig. Determine its adjacency matrix MA.

Representation of Graphs

Solution: Since the directed graph G consists of five vertices. Therefore, the adjacency matrix will be a 5 x 5 matrix. The adjacency matrix of the directed graphs is as follows:

Representation of Graphs

2. Incidence Matrix Representation: If a directed graph G consists of n vertices and m edges, then the incidence matrix is an n x m matrix C = [cij] and defined by

Representation of Graphs

The number of ones in an incidence matrix is equal to the number of edges in the graph.

Example: Consider the directed graph G as shown in fig. Find its incidence matrix MI.

Representation of Graphs

Solution: The directed graph consists of four vertices and five edges. Therefore, the incidence matrix is a 4 x 5 matrix which is show in fig:

Representation of Graphs

(c)Representation of Multigraph:

Represented only by adjacency matrix representation.

(i)Adjacency matrix representation of multigraph: If a multigraph G consists of vertices, then the adjacency matrix of graph is an n x n matrix A = [aij] and is defined by

Representation of Graphs

If there exist one or more than one edges between vertex vi and vj then aij=N, where is the number of edges between vi and vj.

If there is no edge between vi and vj.

Example: Consider the multigraph shown in Fig, Determine its adjacency matrix.

Representation of Graphs

Solution: Since the multigraph consist of five vertices. Therefore the adjacency matrix will be an 5 x 5 matrix. The adjacency matrix of the multigraph is as follows:

Representation of Graphs


Isomorphic Graphs

Consider a graph G(V, E) and G* (V*,E*) are said to be isomorphic if there exists one to one correspondence i.e. f:V→V* such that {u, v} is an edge of G if and only if {f(u), f(v)} is an edge of G*.

Isomorphic and Homeomorphic Graphs

Number of vertices of graph (a) must be equal to graph (b), i.e., one to one correspondence some goes for edges.

Homeomorphic Graphs:

Two graphs G and G* are said to homeomorphic if they can be obtained from the same graph or isomorphic graphs by this method. The graphs (a) and (b) are not isomorphic, but they are homeomorphic since they can be obtained from the graph (c) by adding appropriate vertices.

Isomorphic and Homeomorphic Graphs

Subgraph:

A subgraph of a graph G=(V, E) is a graph G’=(V’,E’) in which V’⊆V and E’⊆E and each edge of G’ have the same end vertices in G’ as in graph G.

Note: A single vertex is a subgraph.

Example: Consider the graph G shown in fig. Show the different subgraph of this graph.

Isomorphic and Homeomorphic Graphs

Solution: The following are all subgraphs of the above graph as shown in fig:

Isomorphic and Homeomorphic Graphs

Spanning Subgraph:

A graph G1 is called a spanning subgraph of G if G1 contains all the vertices of G.

Example: The following fig is the spanning subgraph of the graph shown in Fig:

Isomorphic and Homeomorphic Graphs


Complete Graph

A graph G is said to be complete if every vertex in G is connected to every other vertex in G. Thus a complete graph G must be connected. The complete graph with n vertices is denoted by Kn. The Figure shows the graphs K1 through K6.

Regular and Bipartite Graphs

Regular Graph:

A graph is said to be regular or K-regular if all its vertices have the same degree K. A graph whose all vertices have degree 2 is known as a 2-regular graph. A complete graph Kn is a regular of degree n-1.

Example1: Draw regular graphs of degree 2 and 3.

Solution: The regular graphs of degree 2 and 3 are shown in fig:

Regular and Bipartite Graphs

Example2: Draw a 2-regular graph of five vertices.

Solution: The 2-regular graph of five vertices is shown in fig:

Regular and Bipartite Graphs

Example3: Draw a 3-regular graph of five vertices.

Solution: It is not possible to draw a 3-regular graph of five vertices. The 3-regular graph must have an even number of vertices.

Regular and Bipartite Graphs

Bipartite Graph:

A graph G=(V, E) is called a bipartite graph if its vertices V can be partitioned into two subsets V1 and V2 such that each edge of G connects a vertex of V1 to a vertex V2. It is denoted by Kmn, where m and n are the numbers of vertices in V1 and V2 respectively.

Example: Draw the bipartite graphs K2, 4and K3 ,4.Assuming any number of edges.

Solution: First draw the appropriate number of vertices on two parallel columns or rows and connect the vertices in one column or row with the vertices in other column or row. The bipartite graphs K2,4 and K3,4 are shown in fig respectively.

Regular and Bipartite Graphs

Complete Bipartite Graph:

A graph G = (V, E) is called a complete bipartite graph if its vertices V can be partitioned into two subsets V1 and V2 such that each vertex of V1 is connected to each vertex of V2. The number of edges in a complete bipartite graph is m.n as each of the m vertices is connected to each of the n vertices.

Example: Draw the complete bipartite graphs K3,4 and K1,5.

Solution: First draw the appropriate number of vertices in two parallel columns or rows and connect the vertices in the first column or row with all the vertices in the second column or row. The graphs K3,4 and K1,5 are shown in fig:

Regular and Bipartite Graphs
Regular and Bipartite Graphs

Euler Path:

A Euler Path through a graph is a path whose edge list contains each edge of the graph exactly once.

Euler Circuit: An Euler Circuit is a path through a graph, in which the initial vertex appears a second time as the terminal vertex.

Euler Graph: An Euler Graph is a graph that possesses a Euler Circuit. A Euler Circuit uses every edge exactly once, but vertices may be repeated.

Example: The graph shown in fig is a Euler graph. Determine Euler Circuit for this graph.

Regular and Bipartite Graphs

Solution: The Euler Circuit for this graph is

              V1,V2,V3,V5,V2,V4,V7,V10,V6,V3,V9,V6,V4,V10,V8,V5,V9,V8,V1

We can produce an Euler Circuit for a connected graph with no vertices of odd degrees.

State and Prove Euler’s Theorem:

Statement: Consider any connected planar graph G= (V, E) having R regions, V vertices and E edges. Then V+R-E=2.

Proof: Use induction on the number of edges to prove this theorem.

Basis of Induction: Assume that each edge e=1.Then we have two cases, graphs of which are shown in fig:

Regular and Bipartite Graphs

In Fig: we have V=2 and R=1. Thus 2+1-1=2

In Fig: we have V=1 and R=2. Thus 1+2-1=2.

Hence, the basis of induction is verified.

Induction Step: Let us assume that the formula holds for connected planar graphs with K edges.

Let G be a graph with K+1 edge.

Firstly, we suppose that G contains no circuits. Now, take a vertex v and find a path starting at v.Since G is a circuit free, whenever we find an edge, we have a new vertex. At last, we will reach a vertex v with degree1. So we cannot move further as shown in fig:

Now remove vertex v and the corresponding edge incident on v. So, we are left with a graph G* having K edges as shown in fig:

Regular and Bipartite Graphs

Hence, by inductive assumption, Euler’s formula holds for G*.

Now, since G has one more edge than G*, one more vertex than G* with same number of regions as in G*. Hence, the formula also holds for G.

Secondly, we assume that G contains a circuit and e is an edge in the circuit shown in fig:

Regular and Bipartite Graphs

Now, as e is the part of a boundary for two regions. So, we only remove the edge, and we are left with graph G* having K edges.

Hence, by inductive assumption, Euler’s formula holds for G*.

Now, since G has one more edge than G*, one more region than G* with the same number of vertices as G*. Hence the formula also holds for G which, verifies the inductive steps and hence proves the theorem.


Planar Graph:

A graph is said to be planar if it can be drawn in a plane so that no edge cross.

Example: The graph shown in fig is planar graph.

Planar and Non-Planar Graphs
Planar and Non-Planar Graphs

Region of a Graph: Consider a planar graph G=(V,E).A region is defined to be an area of the plane that is bounded by edges and cannot be further subdivided. A planar graph divides the plans into one or more regions. One of these regions will be infinite.

Finite Region: If the area of the region is finite, then that region is called a finite region.

Infinite Region: If the area of the region is infinite, that region is called a infinite region. A planar graph has only one infinite region.

Example: Consider the graph shown in Fig. Determine the number of regions, finite regions and an infinite region.

Planar and Non-Planar Graphs

Solution: There are five regions in the above graph, i.e. r1,r2,r3,r4,r5.

There are four finite regions in the graph, i.e., r2,r3,r4,r5.

There is only one finite region, i.e., r1

Properties of Planar Graphs:

  1. If a connected planar graph G has e edges and r regions, then r ≤Planar and Non-Planar Graphse.
  2. If a connected planar graph G has e edges, v vertices, and r regions, then v-e+r=2.
  3. If a connected planar graph G has e edges and v vertices, then 3v-e≥6.
  4. A complete graph Kn is a planar if and only if n<5.
  5. A complete bipartite graph Kmn is planar if and only if m<3 or n>3.

Example: Prove that complete graph K4 is planar.

Solution: The complete graph K4 contains 4 vertices and 6 edges.

We know that for a connected planar graph 3v-e≥6.Hence for K4, we have 3×4-6=6 which satisfies the property (3).

Thus K4 is a planar graph. Hence Proved.

Non-Planar Graph:

A graph is said to be non planar if it cannot be drawn in a plane so that no edge cross.

Example: The graphs shown in fig are non planar graphs.

Planar and Non-Planar Graphs

These graphs cannot be drawn in a plane so that no edges cross hence they are non-planar graphs.

Properties of Non-Planar Graphs:

A graph is non-planar if and only if it contains a subgraph homeomorphic to K5 or K3,3

Example1: Show that K5 is non-planar.

Solution: The complete graph K5 contains 5 vertices and 10 edges.

Now, for a connected planar graph 3v-e≥6.

Hence, for K5, we have 3 x 5-10=5 (which does not satisfy property 3 because it must be greater than or equal to 6).

Thus, K5 is a non-planar graph.

Example2: Show that the graphs shown in fig are non-planar by finding a subgraph homeomorphic to K5 or K3,3.

Planar and Non-Planar Graphs
Planar and Non-Planar Graphs

Solution: If we remove the edges (V1,V4),(V3,V4)and (V5,V4) the graph G1,becomes homeomorphic to K5.Hence it is non-planar.

If we remove the edge V2,V7) the graph G2 becomes homeomorphic to K3,3.Hence it is a non-planar.

Graph Coloring:

Suppose that G= (V,E) is a graph with no multiple edges. A vertex coloring of G is an assignment of colors to the vertices of G such that adjacent vertices have different colors. A graph G is M-Colorable if there exists a coloring of G which uses M-Colors.

Proper Coloring: A coloring is proper if any two adjacent vertices u and v have different colors otherwise it is called improper coloring.

Example: Consider the following graph and color C={r, w, b, y}.Color the graph properly using all colors or fewer colors.

Planar and Non-Planar Graphs

The graph shown in fig is a minimum 3-colorable, hence x(G)=3

Solution: Fig shows the graph properly colored with all the four colors.

Planar and Non-Planar Graphs

Fig shows the graph properly colored with three colors.

Planar and Non-Planar Graphs

Chromatic number of G: The minimum number of colors needed to produce a proper coloring of a graph G is called the chromatic number of G and is denoted by x(G).

Example: The chromatic number of Kn is n.

Solution: A coloring of Kn can be constructed using n colours by assigning different colors to each vertex. No two vertices can be assigned the same colors, since every two vertices of this graph are adjacent. Hence the chromatic number of Kn=n.

Applications of Graph Coloring

Some applications of graph coloring include:

  • Register Allocation
  • Map Coloring
  • Bipartite Graph Checking
  • Mobile Radio Frequency Assignment
  • Making a time table, etc.

State and prove Handshaking Theorem.

Handshaking Theorem: The sum of degrees of all the vertices in a graph G is equal to twice the number of edges in the graph.

Mathematically it can be stated as:

              ∑v∈Vdeg(v)=2e

Proof: Let G = (V, E) be a graph where V = {v1,v2, . . . . . . . . . .} be the set of vertices and E = {e1,e2 . . . . . . . . . .} be the set of edges. We know that every edge lies between two vertices so it provides degree one to each vertex. Hence each edge contributes degree two for the graph. So the sum of degrees of all vertices is equal to twice the number of edges in G.

Hence,         ∑v∈Vdeg(v)=2e


Dijkstra’s Algorithm:

This algorithm maintains a set of vertices whose shortest paths from source is already known. The graph is represented by its cost adjacency matrix, where cost is the weight of the edge. In the cost adjacency matrix of the graph, all the diagonal values are zero. If there is no path from source vertex Vs to any other vertex Vi then it is represented by +∞.In this algorithm, we have assumed all weights are positive.

  1. Initially, there is no vertex in sets.
  2. Include the source vertex Vs in S.Determine all the paths from Vs to all other vertices without going through any other vertex.
  3. Now, include that vertex in S which is nearest to Vs and find the shortest paths to all the vertices through this vertex and update the values.
  4. Repeat the step until n-1 vertices are not included in S if there are n vertices in the graph.

After completion of the process, we got the shortest paths to all the vertices from the source vertex.

Example: Find the shortest paths between K and L in the graph shown in fig using Dijkstra’s Algorithm.

Dijkstra's Algorithm

Solution:

Step1: Include the vertex K is S and determine all the direct paths from K to all other vertices without going through any other vertex.

Distance to all other vertices

SKabcdL
K04(K)2(K)20(K)

Step2: Include the vertex in S which is nearest to K and determine shortest paths to all vertices through this vertex and update the values. The closest vertex is c.

Distance to all other vertices

SKabcdL
K03(K, c)7(K, c)2(K)8(K, c)18(K, c)

Step3: The vertex which is 2nd nearest to K is 9, included in S.

Distance to all other vertices

SKabcdL
K03(K, c)7(K, c)2(K)7(K, c, a)18(K, c)

Step4: The vertex which is 3rd nearest to K is b, included in S.

Distance to all other vertices

SKabcdL
K03(K, c)7(K, c)2(K)7(K, c, a)8(K, c, b)

Step5: The vertex which is next nearest to K is d, is included in S.

Distance to all other vertices

SKabcdL
K(c, a, b, d)03(K, c)7(K, c)2(K)7(K, c, a)8(K, c, b)

Since, n-1 vertices included in S. Hence we have found the shortest distance from K to all other vertices. Thus, the shortest distance between K and L is 8 and the shortest path is K, c, b, L.


Travelling Salesman Problem

Suppose a salesman wants to visit a certain number of cities allotted to him. He knows the distance of the journey between every pair of cities. His problem is to select a route the starts from his home city, passes through each city exactly once and return to his home city the shortest possible distance. This problem is closely related to finding a Hamiltonian circuit of minimum length. If we represent the cities by vertices and road connecting two cities edges we get a weighted graph where, with every edge ei a number wi(weight) is associated.

A physical interpretation of the above abstract is: consider a graph G as a map of n cities where w (i, j) is the distance between cities i and j. A salesman wants to have the tour of the cities which starts and ends at the same city includes visiting each of the remaining a cities once and only once.

In the graph, if we have n vertices (cities), then there is (n-1)! Edges (routes) and the total number of Hamiltonian circuits in a complete graph of n vertices will beTravelling Salesman Problem.

Nearest Neighbour Method:

This procedure gives reasonably good results for the travelling salesman problem. The method is as follows:

Step1: Select an arbitrary vertex and find the vertex that is nearest to this starting vertex to form an initial path of one edge.

Step2: Let v denote the latest vertex that was added to the path. Now, among the result of the vertices that are not in the path, select the closest one to v and add the path, the edge-connecting v and this vertex. Repeat this step until all the vertices of graph G are included in the path.

Step3: Join starting vertex and the last vertex added by an edge and form the circuit.

Example: Use the nearest-neighbor method to solve the following travelling salesman problem, for the graph shown in fig starting at vertex v1.

Travelling Salesman Problem

Solution: We have to start with vertex v1. By using the nearest neighbor method, vertex by vertex construction of the tour or Hamiltonian circuit is shown in fig:

Travelling Salesman Problem

The total distance of this route is 18.

Discrete Mathematics Forum

https://eduraryhub.com/forums/forum/discrete-mathematics-forum/

Related Articles

Responses