# 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}.

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.

**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:

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

=d (v_{1})+d(v_{2} )+d(v_{3} )+d(v_{4} )+d(v_{5} )+d(v_{6} )+d(v_{7} )+d(v_{8})

= 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:

**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.

**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.**An Elementary Path:**The path is called elementary one if no vertex is repeated in the path, i.e., all the vertices are distinct.**Circuit or Closed Path:**The circuit or closed path is a path in which starts and ends at the same vertex, i.e., v_{0}=v_{n}.**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:

- A simple path fromV
_{1}to V_{6}. - An elementary path from V
_{1}to V_{6}. - A simple path which is not elementary from V
_{1}to V_{6}. - A path which is not simple and starting fromV
_{2}. - A simple circuit starting from V
_{1} - A circuit which is not simple and starting from V
_{2}.

**Solution:**

- A simple path fromV
_{1}to V_{6}.

V_{1,}V_{2,}V_{3,}V_{4,}V_{5,}V_{6}. - An elementary path from V
_{1}to V_{6}.

V_{1,}V_{2,}V_{3,}V_{5,}V_{4,}V_{6}. - A simple path which is not elementary from V
_{1}to V_{6}.

V_{1,}V_{2,}V_{3,}V_{5,}V_{2,}V_{4,}V_{6}. - A path which is not simple and starting fromV
_{2}.

V_{2,}V_{3,}V_{4,}V_{5,}V_{3,}V_{4,}V_{6}. - A simple circuit starting fromV
_{1}.

V_{1,}V_{2,}V_{4,}V_{6,}V_{5,}V_{3,}V_{1} - A circuit which is not simple and starting from V
_{2}.

V_{2,}V_{3,}V_{1,}V_{2,}V_{5,}V_{4,}V_{2}.

**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:

Determine the following:

- Pendant Vertices
- Pendant Edges
- Odd vertices
- Even Vertices
- Incident Edges
- Adjacent Vertices

**Solution:**

- The vertex V
_{5}is the pendant vertex. - The edge (V
_{4,}V_{5}) or e_{5}is the pendant edge. - The vertices V
_{3}and V_{5}are odd vertices. - The vertices V
_{1,}V_{2,}and V_{4}are even vertices. - The edge e
_{1}is an incident on V_{1,}and V_{2}.

The edge e_{2}is an incident on V_{1}and V_{3}.

The edge e_{3}is an incident on V_{2}and V_{3}.

The edge e_{4}is an incident on V_{3}and V_{4}.

The edge e_{5}is an incident on V_{4}and V_{5}. - The vertex V
_{1}is adjacent to V_{2}and V_{3}.

The vertex V_{2}is adjacent to V_{1}and V_{2}.

The vertex V_{3}is adjacent to V_{1}and V_{4}

The vertex V_{4}is adjacent to V_{3}and V_{5}

The vertex V_{5}is adjacent to V_{4}.

**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.

**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.

**Solution:** For this graph, the edge set {(V_{1,}V_{5}),(V_{7,}V_{5})} 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-v_{1} (ii) G-v_{3} (iii) G-v_{5}

**Solution:**

- The subgraph G-v
_{1}is shown in fig - The subgraph G-v
_{3}is shown in fig - The subgraph G-v
_{5}is shown in fig

**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-e_{1} (ii) G-e_{3} (iii) G-e_{4}

**Solution:**

- The subgraph G-e
_{1}is shown in fig - The subgraph G-e
_{3}is shown in fig - The subgraph G-e
_{4}is shown in fig

# 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.

**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:

**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.

**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.

**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 K_{n}.A complete graph with n vertices will have edges.

**Example:** Draw Undirected Complete Graphs k_{4}and k_{6}.

**Solution:** The undirected complete graph of k_{4} is shown in fig1 and that of k_{6}is shown in fig2.

**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.

**Solution:**

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

{V_{1,}V_{2,}V_{3,}V_{4}},{V_{5,}V_{6,}V_{7,}V_{8}} and {V_{9,}V_{10}}.

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

{V_{1,}V_{2}},{V_{3,}V_{4}},{V_{5,}V_{6}},{V_{7,}V_{8}},{V_{9,}V_{10}}and {V_{11,}V_{12}}.

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

**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.

**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 K_{n}.

**Example:** Draw directed complete graphs K_{3} and K_{5}.

**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:

**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.

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

**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}, {e_{1,}e_{2,}e_{3,}e_{4}}}

**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.

# 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 = [a_{ij}] and defined by

If there exists an edge between vertex v_{i} and v_{j}, where i is a row and j is a column then the value of a_{ij}=1.

If there is no edge between vertex v_{i} and v_{j}, then value of a_{ij}=0.

**Example:** Find the adjacency matrix M_{A} of graph G shown in Fig:

**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:

**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 = [c_{ij}] and defined by

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 M_{I}.

**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:

## (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 = [a_{ij}] and defined by

If there exists an edge between vertex V_{i} and V_{j}, with V_{i} as initial vertex and V_{j} as a final vertex, then the value of a_{ij}=1.

If there is no edge between vertex V_{i} and V_{j}, then the value of a_{ij}=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 M_{A}.

**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:

**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 = [c_{ij}] and defined by

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 M_{I}.

**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:

## (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 = [a_{ij}] and is defined by

If there exist one or more than one edges between vertex v_{i} and v_{j} then a_{ij}=N, where is the number of edges between v_{i} and v_{j}.

If there is no edge between v_{i} and v_{j}.

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

**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:

# 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*.

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.

## 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.

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

## Spanning Subgraph:

A graph G_{1} is called a spanning subgraph of G if G_{1} contains all the vertices of G.

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

# 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 K_{n}. The Figure shows the graphs K_{1} through K_{6}.

## 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 K_{n} 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:

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

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

**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.

## Bipartite Graph:

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

**Example:** Draw the bipartite graphs K_{2}, 4and K_{3} ,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 K_{2,4} and K_{3,4} are shown in fig respectively.

## Complete Bipartite Graph:

A graph G = (V, E) is called a complete bipartite graph if its vertices V can be partitioned into two subsets V_{1} and V_{2} such that each vertex of V_{1} is connected to each vertex of V_{2}. 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 K_{3,4} and K_{1,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 K_{3,4} and K_{1,5} are shown in fig:

## 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.

**Solution:** The Euler Circuit for this graph is

V_{1},V_{2},V_{3},V_{5},V_{2},V_{4},V_{7},V_{10},V_{6},V_{3},V_{9},V_{6},V_{4},V_{10},V_{8},V_{5},V_{9},V_{8},V_{1}

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:

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:

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:

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.

**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.

**Solution:** There are five regions in the above graph, i.e. r_{1},r_{2},r_{3},r_{4},r_{5}.

There are four finite regions in the graph, i.e., r_{2},r_{3},r_{4},r_{5}.

There is only one finite region, i.e., r_{1}

## Properties of Planar Graphs:

- If a connected planar graph G has e edges and r regions, then r â‰¤e.
- If a connected planar graph G has e edges, v vertices, and r regions, then v-e+r=2.
- If a connected planar graph G has e edges and v vertices, then 3v-eâ‰¥6.
- A complete graph K
_{n}is a planar if and only if n<5. - A complete bipartite graph K
_{mn}is planar if and only if m<3 or n>3.

**Example:** Prove that complete graph K_{4} is planar.

**Solution:** The complete graph K_{4} contains 4 vertices and 6 edges.

We know that for a connected planar graph 3v-eâ‰¥6.Hence for K_{4}, we have 3×4-6=6 which satisfies the property (3).

Thus K_{4} 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.

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 K_{5} or K_{3,3}

**Example1:** Show that K_{5} is non-planar.

**Solution:** The complete graph K_{5} contains 5 vertices and 10 edges.

Now, for a connected planar graph 3v-eâ‰¥6.

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

Thus, K_{5} is a non-planar graph.

**Example2:** Show that the graphs shown in fig are non-planar by finding a subgraph homeomorphic to K_{5} or K_{3,3}.

**Solution:** If we remove the edges (V_{1},V_{4}),(V_{3},V_{4})and (V_{5},V_{4}) the graph G_{1},becomes homeomorphic to K_{5}.Hence it is non-planar.

If we remove the edge V_{2,V}7) the graph G_{2} becomes homeomorphic to K_{3,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.

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.

Fig shows the graph properly colored with three colors.

**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 K_{n} is n.

**Solution:** A coloring of K_{n} 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 K_{n}=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âˆˆV}deg(v)=2e

**Proof:** Let G = (V, E) be a graph where V = {v_{1},v_{2}, . . . . . . . . . .} be the set of vertices and E = {e_{1},e_{2} . . . . . . . . . .} 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âˆˆV}deg(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 V_{s} to any other vertex V_{i} then it is represented by +âˆž.In this algorithm, we have assumed all weights are positive.

- Initially, there is no vertex in sets.
- Include the source vertex V
_{s}in S.Determine all the paths from V_{s}to all other vertices without going through any other vertex. - Now, include that vertex in S which is nearest to V
_{s}and find the shortest paths to all the vertices through this vertex and update the values. - 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.

**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**

S | K | a | b | c | d | L |

K | 0 | 4(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**

S | K | a | b | c | d | L |

K | 0 | 3(K, c) | 7(K, c) | 2(K) | 8(K, c) | 18(K, c) |

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

**Distance to all other vertices**

S | K | a | b | c | d | L |

K | 0 | 3(K, c) | 7(K, c) | 2(K) | 7(K, c, a) | 18(K, c) |

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

**Distance to all other vertices**

S | K | a | b | c | d | L |

K | 0 | 3(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**

S | K | a | b | c | d | L |

K(c, a, b, d) | 0 | 3(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 e_{i} a number w_{i}(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 be.

## 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 v_{1}.

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

The total distance of this route is 18.

## Responses