Graph Theory

Colour Problem

3 min read
The Five colour theorem: Every planar graph is 5-colorable. Proof. We proceed by induction on the number P of points. For any planar graph having P ≤ 5 points, the result follows trivially since the graph is P-colorable. As the inductive hypothesis we assume that all planar graphs with P points, P ≥ 5, are 5-colourable. Let G be a plane graph with P 1 vertices, G contains a vertex v of degree 5 or less. By hypothesis, the plane graph G – v is 5-colourable. Consider an assignment of colours to the vertices of G – v so that a 5-colouring results, when the colours are denoted by Ci, 1 ≤ i ≤ 5. Certainly, if some colour, say Cj, is not used in the colouring of the vertices adjacent with v, then by assigning the colour Cj to v, a 5-colouring of G results. This leaves only the case to consider in which deg v = 5 and five colours are used for the vertices of G adjacent with v. Permute the colours, if necessary, so that the vertices coloured C1, C2, C3, C4 and C5 are arranged cyclically about v, Now label the vertex adjacent with v and coloured Ci by vi, 1 ≤ i ≤ 5 (see Figure 2.100) Let G13 denote the subgraph of G – v induced by those vertices coloured C1 or C3. If v1 and v3 belong to different components of G13, then a 5-coloring of G – v may be accomplished by interchanging the colors of the vertices in the component of G13 containing v1. In this 5-coloring however, no vertex adjacent with v is colored C1, so by coloring v with the color C1, a 5-coloring of G results.

Travelling Salesman Problem

3 min read
TRAVELING-SALESMAN PROBLEM: The traveling-salesman problem, stated as follows : ‘‘A salesman is required to visit a number of cities during a trip. Given the distances between the cities, in what order should he travel so as to visit every city precisely once and return home, with the minimum mileage traveled ?’’Representing the cities by vertices and the roads between them by edges. We get a graph. In this graph, with every edge ei there is associated a real number (the distance in miles, say), w(ei). Such a graph is called a weighted graph ; w(ei) being the weight of edge ei. (i.e., A traveling salesman wants to visit each of n cities exactly once and return to his starting point) if each of the cities has a road to very other city, we have a complete weighted grap. For example, suppose that the salesman wants to visit five cities, namely, A, B, C, D and E (see Figure). In which order should he visit these cities to travel the minimum total distance ? To solve this problem we can assume the salesman starts in A (since this must be part of the circuit) and examine all possible ways for him to visit the other four cities and then return to A (starting elsewhere will produce the same circuits). There are a total of 24 such circuits, but since we travel the same distance when we travel a circuit in reverse order, we need only consider 12 different circuits to find the minimum total distance he must travel. We list these 12 different circuits and the total distance traveled for each circuit. As can be seen from the list, the minimum total distance of 458 miles is traveled using the circuit A – B – E – D – C – A (or its reverse).

Transport Networks

4 min read
Transport Network: Let N = (V, E) be a loop-free connected directed graph. Then N is called a network, or transport network, if the following conditions are satisfied : (i) There exists a unique vertex a ∈ V with id(a), the in degree of a, equal to O. This vertex a is called the source. (ii) There is a unique vertex z ∈ V, called the sink, where od(z), the out degree of z, equals O. (iii) The graph N is weighted, so there is a function from E to the set of non negative integers that assigns to each edge e = (v, w) ∈ E a capacity, denoted by c(e) = c(v, w). If N = (V, E) is a transport network, a function f from E to the non negative integers is called a flow for N if (i) f(e) ≤ c(e) for each edge e ∈ E, and (ii) for each v ∈ V, other than the source a or the sink z, If there is no edge (v, w), then f(v, w) = 0. Let f be a flow for a transport network N = (V, E) (i) An edge e of the network is called saturated if f(e) = c(e). When f(e) < c(e), the edge is called unsaturated. (ii) If a is the source of N, then val(f) = is called the value of the flow. If N = (V, E) is a transport network and C is a cut-set for the undirected graph associated with N, then C is called a cut, or an a–z cut, if the removal of the edges in C from the network results in the separation of a and z. For example, the graph in Fig. (4.67) is a transport network. Here vertex a is the source, the sink is at vertex z, and capacities are shown beside each edge. Since c(a, b) c(a, g) = 5 7 = 12, the amount of the commodity being transported from a to z cannot exceed 12. With c(d, z) c(h, z) = 5 6 = 11, the amount is further restricted to be no greater than 11.

Spanning Tree

3 min read
Introduction: A spanning tree is a spanning subgraph, that is a tree. In Other words a spanning tree for a connected graph G is a subgraph of G that is a tree and whose vertex set is all the vertices of G. If G is a tree then it has only one spanning tree, G itself. If G is not a tree it has more than one spanning tree. Consider the following problem. In the diagram shown below we have four wells in an offshore oilfield (nodes 1 to 4 below) and an on-shore terminal (node 5 below). The four wells in this field must be connected together via a pipeline network to the on-shore terminal. The various pipelines that can be constructed are shown as links in the diagram below and the cost of each pipeline is given next to each link. What pipelines would you recommend be built?

Algorithm For Constructing Spanning Trees

3 min read
ALGORITHMS FOR CONSTRUCTING SPANNING TREES An algorithm for finding a spanning tree based on the proof of the theorem : A simple graph G has a spanning tree if and only if G is connected, would not be very efficient, it would involve the time-consuming process of finding cycles. Instead of constructing spanning trees by removing edges, spanning tree can be built up by successively adding edges. Two algorithms based on this principle for finding a spanning tree are Breath-first search (BFS) and Depth-first search (DFS). BFS algorithm In this algorithm a rooted tree will be constructed, and underlying undirected graph of this rooted forms the spanning tree. The idea of BFS is to visit all vertices on a given level before going into the next level. Procedure : (i) Arbitrarily choose a vertex and designate it as the root. Then add all edges incident to this vertex, such that the addition of edges does not produce any cycle. (ii) The new vertices added at this stage become the vertices at level 1 in the spanning tree, arbitrarily order them. (iii) Next, for each vertex at level 1, visited in order, add each edge incident to this vertex to the tree as long as it does not produce any cycle. (iv) Arbitrarily order the children of each vertex at level 1. This produces the vertices at level 2 in the tree. (v) Continue the same procedure until all the vertices in the tree have been added. (vi) The procedure ends, since there are only a finite number of edges in the graph. (vii) A spanning tree is produced since we have produced a tree without cycle containing every vertex of the graph.

Prim’s Algorithm

7 min read
Prim’s algorithm: Let G = (V, E) be a connected graph with | V | = n. To find the adjacency matrix for G. Now proceed according to the following steps : Step 1 : Select a vertex v1 ∈ V and arrange the adjacency matrix of the graph in such a way that the first row and first column of the matrix corresponds to V1. Step 2 : Choose a vertex v2 of V such that (v1, v2) ∈ E. Merge v1 and v2 into a new vertex, call it vmi and drop v2. Replace v1 by vmi in the graph. Find the new adjacency matrix corresponding to this new quotient graph. Step 3 : While merging select an edge from those edges which are going to be removed (or merged with other edge) from the graph. Keep a record of it. Step 4 : Repeat steps 1, 2 and 3 until all vertices have been merged into one vertex. Step 5 : Now construct a tree from the edges, collected at different iterations of the algorithm. The same Prim’s algorithm with little modification can be used to find a minimum spanning tree for a weighted graph. The stepwise algorithm is given below. Let G = (V, E) be graph and S = (Vs, Es) be the spanning tree to be found from G. Step 1 : Select a vertex v1 of V and initialize Vs = {v1} and Es = {} Step 2 : Select a nearest neighbour of vi from V that is adjacent to same vj ∈ Vs and that edge (vi, vj) does not form a cycle with members edge of Es. Set Vs = Vs ∪ {vi} and Es = Es ∪ {(vi, vj)} Step 3 : Repeat step 2 until | Es | = | V | – 1. Theorem 4.5. Prim’s algorithms produces a minimum spanning tree of a connected weighted graph. Proof. Let G be a connected weighted graph. Suppose that the successive edges chosen by Prim’s algorithm are e1, e2, ..., en – 1. Let S be the tree with e1, e2, ..., en – 1 as its edges, and let Sk be the tree with e1, e2, ..., ek as its edges. Let T be a minimum spanning tree of G containing the edges e1, e2, ..., ek, where k is the maximum integer with the property that a minimum spanning tree exists containing the first k edges chosen by Prim’s algorithm. The theorem follows if we can show that S = T. Suppose that S ≠ T, so that k < n – 1. Consequently, T contains e1, e2, ..., ek, but not ek 1. Consider the graph made up of T together with ek 1. Since this graph is connected and has n edges, too many edges to be a tree, it must contain a simple circuit. This simple circuit must contain ek 1 since there was no simple circuit in T. Furthermore, there must be an edge in the simple circuit that does not belong to Sk 1 since Sk 1 is a tree. By starting at an end point of ek 1 that is also an endpoint of one of the edges e1, ..., ek, and following the circuit until it reaches an edge not in Sk 1, we can find an edge e not in Sk 1 that has an end point that is also an end point of one of the edges e1, e2, ..., ek. By deleting e from T and adding ek 1, we obtain a tree T′ with n – 1 edges (it is a tree since it has no simple circuits).