Category: 08. Graph Theory

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

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…

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 Graph: A graph is said to be regular…

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.,…

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…

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…

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…