By the end of this chapter you should be familiar with:
A graph is defined as set of vertices and a set of edges. A vertex represents an object. An edge joins two vertices.
A graph with no loops and no parallel edges is called a simple graph.
In a directed graph, each edge has a direction.
A graph G is said to be connected if there exists a path between every pair of vertices. There should be at least one edge for every vertex in the graph. So that we can say that it is connected to some other vertex at the other side of the edge.
The degree (or order) of a vertex in a graph is the number of edges with that vertex as an end point.
A vertex whose degree is an even number is said to have an even degree or even vertex.
The in-degree of a vertex in a directed graph is the number of edges with that vertex as an end point. The out-degree of a vertex in a directed graph is the number of edges with that vertex as a starting point.
A graph having no edges is called a Null Graph.
A simple graph with ‘n’ mutual vertices is called a complete graph and it is denoted by ‘Kn’. In the graph, a vertex should have edges with all other vertices, then it called a complete graph.
In other words, if a vertex is connected to all other vertices in a graph, then it is called a complete graph.
A simple graph G = (V, E) with vertex partition V = {V1, V2} is called a bipartite graph if every edge of E joins a vertex in V1 to a vertex in V2.
In general, a Bipartite graph has two sets of vertices, let us say, V1 and V2, and if an edge is drawn, it should connect any vertex in set V1 to any vertex in set V2.
A bipartite graph ‘G’, G = (V, E) with partition V = {V1, V2} is said to be a complete bipartite graph if every vertex in V1 is connected to every vertex of V2.
In general, a complete bipartite graph connects each vertex from set V1 to each vertex from set V2.
Example: The following graph is a complete bipartite graph because it has edges connecting each vertex from set V1 to each vertex from set V2.
If |V1| = m and |V2| = n, then the complete bipartite graph is denoted by Km, n.
In general, a complete bipartite graph is not a complete graph.
Km,n is a complete graph if m=n=1.
The maximum number of edges in a bipartite graph with n vertices is n2/4
If n = 10, k5, 5 = n2/4 = 100/4 = 25
Similarly,
K6, 4 = 24
K7, 3 = 21
K8, 2 = 16
K9, 1 = 9
If n = 9, k5, 4 = n2/4 = 81/4 = 20
Similarly,
K6, 3 = 18
K7, 2 = 14
K8, 1 = 8
‘G’ is a bipartite graph if ‘G’ has no cycles of odd length. A special case of bipartite graph is a star graph.
For a graph with |V| vertices, an adjacency matrix is a ∣V∣×∣V∣ matrix of 0s and 1s, where the entry in row i and column j is 1 if and only if the edge (i, j) is in the graph. If you want to indicate an edge weight, put it in the row i, column j entry, and reserve a special value (perhaps null) to indicate an absent edge. Here’s the adjacency matrix for the social network graph:
Example:
INCIDENCE MATRICES
Let G be a graph with n vertices, m edges and without self-loops. The incidence matrix A of G is an n × m matrix A = [aij] whose n rows correspond to the n vertices and the m columns correspond to m edges such that:
ai,j = 1 if jth edge mj is incident on the ith vertex else it’s 0.
Example:
The transition matrix A associated to a directed graph is defined as follows. If there is an edge from i to j and the outdegree of vertex i is di, then on column i and row j we put 1/di. Otherwise we mark column i, row j with zero. Notice that we first look at the column, then at the row. We usually write 1/di on the edge going from vertex i to an adjacent vertex j, thus obtaining a weighted graph.
Example: Then the transition matrix associated to it is:
In general, a matrix is called primitive if there is a positive integer k such that Ak is a positive matrix. A graph is called connected if for any two different nodes i and j there is a directed path either from i to j or from j to i. On the other hand, a graph is called strongly connected if starting at any node i we can reach any other different node j by walking on its edges.
The direction of movement in a transition matrix is opposite to that of an adjacency matrix.
Given an undirected and connected graph G = (V, E), a spanning tree of the graph G is a tree that spans G (that is, it includes every vertex of G) and is a subgraph of G (every edge in the tree belongs to G)
A cycle is walk that begins and ends at the same vertex.
The cost of the spanning tree is the sum of the weights of all the edges in the tree. There can be many spanning trees. Minimum spanning tree is the spanning tree where the cost is minimum among all the spanning trees. There also can be many minimum spanning trees.
Minimum spanning tree has direct application in the design of networks. It is used in algorithms approximating the travelling salesman problem, multi-terminal minimum cut problem and minimum-cost weighted perfect matching.
Kruskal’s Algorithm builds the spanning tree by adding edges one by one into a growing spanning tree. Kruskal’s algorithm follows greedy approach as in each iteration it finds an edge which has least weight and add it to the growing spanning tree.
Algorithm Steps:
Prim’s Algorithm also use Greedy approach to find the minimum spanning tree. In Prim’s Algorithm we grow the spanning tree from a starting position. Unlike an edge in Kruskal’s, we add vertex to the growing spanning tree in Prim’s.
Algorithm Steps:
A connected graph G is Eulerian if there exists a closed trail containing every edge of G. Such a trail is an Eulerian trail. Note that this definition requires each edge to be traversed once and once only, A non-Eulerian graph G is semi-Eulerian if there exists a trail containing every edge of G.
A trail is walk that repeats no edges. A circuit is a trail that starts and finishes at the same vertex.
The problem is how to find a shortest closed walk of the graph in which each edge is traversed at least once, rather than exactly once. In graph theory, an Euler cycle in a connected, weighted graph is called the Chinese Postman problem.
To find a minimum Chinese postman route we must walk along each edge at least once and in addition we must also walk along the least pairings of odd vertices on one extra occasion. An algorithm for finding an optimal Chinese postman route is:
Example:
A path is a walk which does not pass through any vertex more than once. A cycle is a walk that begins and ends at the same vertex, but otherwise does not pass through any vertex more than once.
A Hamiltonian path or cycle is a path or cycle which passes through all the vertices in a graph.
The classical travelling salesman problem (TSP) is to find the Hamiltonian cycle of least weight in a complete weighted graph.
The practical TSP is to find the walk of least weight that passes through each vertex of a graph. In this case the graph need not be complete.
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 be (n – 1)!/2
An upper bound can be found using the nearest neighbour algorithm:
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.
This will always produce a valid Hamiltonian cycle, and therefore must be at least as long as the minimum cycle. Hence, it is an upper bound. By choosing different starting vertices, a number of different upper bounds can be found.
The best upper bound is the upper bound with the smallest value.
Lower bounds can be found by using spanning trees. Since removal of one edge from any Hamilton cycle yields a spanning tree, we see that solution to TSP > minimum length of a spanning tree (MST).
Consider any vertex v in the graph G. Any Hamilton cycle in G has to consist of two edges from v, say vu and vw, and a path from u to w in the graph G \ {v} obtained from G by removing v and its incident edges. Since this path is a spanning tree of G \ {v}, we have Solution to TSP ≥ (sum of lengths of two shortest edges from v) + (MST of G \ {v}).
An alternative is to use the deleted vertex algorithm.
The method for finding a lower bound:
Example 1: Use the nearest-neighbour method to solve the following travelling salesman problem, for the graph shown in fig starting at vertex v1.
Solution: We have to start with vertex v1. By using the nearest neighbour method, vertex by vertex construction of the tour or Hamiltonian circuit is shown in fig:
The total distance of this route is 18.
Example 2: Find a lower bound by deleting vertex A from the graph.
Solution: With the vertex A deleted, the minimum spanning tree is:
This has weight = 25.
The two deleted edges of least weight have weights of 4 and 5.
Lower bound = 25 + 5 + 4 = 34