Applications of Graph Theory in Real Life Sharathkumar. A, Final year, Dept of CSE, Anna University, Villupuram Email: [email protected] com Ph. No: 9789045956 Abstract Graph theory is becoming increasingly significant as it is applied to other areas of mathematics, science and technology. It is being actively used in fields as varied as biochemistry (genomics), electrical engineering (communication networks and coding theory), computer science (algorithms and computation) and operations research (scheduling).

The powerful combinatorial methods found in graph theory have also been used to prove fundamental results in other areas of pure mathematics. We discuss about computer network security (worm propagation) using minimum vertex covers in graphs. We also show how to apply edge coloring and matching in graphs for scheduling (the timetabling problem) and vertex coloring in graphs for map coloring and the assignment of frequencies in GSM mobile phone networks.

Finally, we revisit the classical problem of finding re-entrant knight’s tours on a chessboard using Hamiltonian circuits in graphs. Introduction Graph theory is rapidly moving into the mainstream of mathematics mainl y because of its applications in diverse fields which include biochemistry (genomics), electrical engineering (communications networks and coding theory), computer science (algorithms and computations) and operations research (scheduling). The wide scope of these and other applications has been well-documented cf. 5] [19]. The powerful combinatorial methods found in graph theory have also been used to prove significant and well-known results in a variety of areas in mathematics itself. An application of matching in graph theory shows that there is a common set of left and right coset representatives of a subgroup in a finite group. This result played an important role in Dharwadker’s 2000 proof of the four-color theorem [8] [18]. The existence of matchings in certain infinite bipartite graphs played n important role in Laczkovich’s affirmative answer to Tarski’s 1925 problem of whether a circle is piecewise congruent to a square. The proof of the existence of a subset of the real numbers R that is non-measurable in the Lebesgue sense is due to Thomas [21]. Surprisingly, this theorem can be proved using only discrete mathematics (bipartite graphs). There are many such examples of applications of graph theory to other parts of mathematics, but they remain scattered in the literature [3][16].

In this paper, we present a few selected applications of graph theory to other parts of mathematics and to various other fields in general. Applications Computer Network Security A team of computer scientists led by Eric Filiol [11] at the Virology and Cryptology Lab, ESAT, and the French Navy, ESCANSIC, have recently used the vertex cover algorithm [6] to simulate the propagation of stealth worms on large computer networks and design optimal strategies for protecting the network against such virus attacks in real-time. Figure 5. 1.

The set {2, 4, 5} is a minimum vertex cover in this computer network The simulation was carried out on a large internet-like virtual network and showed that that the combinatorial topology of routing may have a huge impact on the worm propagation and thus some servers play a more essential and significant role than others. The real-time capability to identify them is essential to greatly hinder worm propagation. The idea is to find a minimum vertex cover in the graph whose vertices are the routing servers and whose edges are the (possibly dynamic) connections between routing servers.

This is an optimal solution for worm propagation and an optimal solution for designing the network defense strategy. Figure 5. 1 above shows a simple computer network and a corresponding minimum vertex cover {2, 4, 5}. TimeTabling Problem In a college there are m professors x1, x2, …, xm and n subjects y1, y2, …, yn to be taught. Given that professor xi is required (and able) to teach subject yj for pij periods (p = [ pij ] is called the teaching requirement matrix), the college administration wishes to make a timetable using the minimum possible number of periods.

This is known as the timetabling problem [4] and can be solved using the following strategy. Construct a bipartite multigraphG with vertices x1, x2, …, xm, y1, y2, …, yn such that vertices xi and yj are connected by pij edges. We presume that in any one period each professor can teach at most one sub ject and that each subject can be taught by at most one professor. Consider, first, a single period. The timetable for this single period corresponds to a matching in the graph and, conversely, each matching corresponds to a possible assignment of professors to subjects taught during this period.

Thus, the solution to the timetabling problem consists of partitioning the edges of G into the minimum number of matchings. Equivalently, we must properly color the edges of G with the minimum number of colors. We shall show yet another way of solving the problem using the vertex coloring algorithm [7]. Recall that the line graph L(G) of G has as vertices the edges of G and two vertices in L(G) are connected by an edge if and only if the corresponding edges in G have a vertex in common. The line graph L(G) is a simple graph and a proper vertex coloring of L(G) yields a proper edge coloring of G using the same number of colors.

Thus, to solve the timetabling problem, it suffices to find a minimum proper vertex coloring of L(G) using [7]. We demonstrate the solution with a small example. Suppose there are four professors x1, x2, x3, x4 and five subjects y1, y2, y3, y4, y5 to be taught [4]. The teaching requirement matrix p = [ pij ] is given below in figure 6. 1. p y1 y2 y3 y4 y5 x1 2 0 1 1 0 x2 0 1 0 1 0 x3 0 1 1 1 0 x4 0 0 0 1 1 Figure 6. 1. The teaching requirement matrix We first construct the bipartite multigraph G shown below in figure 6. 2. Figure 6. 2. The bipartite multigraph G Next, we construct the line graph L(G).

The adjacency matrix of L(G) is given below. 0 1 1 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 1 1 1 0 0 1 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 Figure. The adjacency matrix of L(G) Now, we use the vertex coloring algorithm [7] to find a minimum proper 4-coloring of the vertices of L(G). Figure 6. 3. A minimum proper 4-coloring of the vertices of L(G) Vertex Coloring: (1, green), (2, red), (3, blue), (4, yellow), (5, yellow), (6, green), (7, green), (8, yellow), (9, red), (10, blue), (11, yellow).

This, in turn, yields a minimum proper edge 4 coloring of the bipartite multigraph G: Edge Coloring: ({x1, y1}, green), ({x1, y1}, red), ({x1, y3}, blue), ({x1, y4}, yellow), ({x2, y2}, yellow), ({x2, y4}, green), ({x3, y2}, green), ({x3,y3}, yellow), ({x3, y4}, red), ({x4, y4}, blue), ({x4, y5}, yellow). Interpret the colors green, red, blue, yellow as periods 1, 2, 3, 4 respectively. Then, from the edge coloring of G, we obtain a solution of the given timetabling problem as shown below in figure 6. 5. – 1 2 3 4 x1 y1 y1 y3 y4 x2 y4 – – y2 x3 y2 y4 – y3 x4 – – y4 y5 Figure 6. 5. The timetable Map Coloring

Given a map drawn on the plane or the surface of a sphere, the famous four color theorem asserts that it is always possible to properly color the regions of the map such that no two adjacent regions are assigned the same color, using at most four distinct colors [8][18][1]. For any given map, we can construct its dual graph as follows. Put a vertex inside each region of the map and connect two distinct vertices by an edge if and only if their respective regions share a whole segment of their boundaries in common. Then, a proper vertex coloring of the dual graph yields a proper coloring of the regions of the original map.

Dual graph constructed using graph coloring algorithm Knight’s Tours In 840 A. D. , al-Adli [17], a renowned shatranj (chess) player of Baghdad is said to have discovered the first re-entrant knight’s tour, a sequence of moves that takes the knight to each square on an 8? 8 chessboard exactly once, returning to the original square. Many other re-entrant knight’s tours were subsequently discovered but Euler [10] was the first mathematician to do a systematic analysis in 1766, not only for the 8? 8 chessboard, but for re-entrant knight’s tours on the general n? n chessboard.

Given an n? n chessboard, define a knight’s graph with a vertex corresponding to each square of the chessboard and an edge connecting vertex i with vertex j if and only if there is a legal knight’s move from the square corresponding to vertex i to the square corresponding to vertex j. Thus, a re-entrant knight’s tour on the chessboard corresponds to a Hamiltonian circuit in the knight’s graph. The Hamiltonian circuit algorithm [9][13] has been used to find re-entrant knights tours on chessboards of various dimensions. Figure 8. 1. A re-entrant knight’s tour on the 8? 8 chessboard

Conclusion Till this we have discussed about the applications of graph theory in real life. Graph theory is an open ended field and it can be applied to solve various problems in real life. References [1] K. Appel and W. Haken, Every Planar Map is Four Colorable, [2] L. Babai, Some applications of graph contractions, J. Graph Theory, Vol. 1 (1977) 125-130. [3] E. Bertram and P. Horak, Some applications of graph theory to other parts of mathematics, [4] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, [5] L. Caccetta and K. Vijayan, Applications of graph theory, [6]

Ashay Dharwadker, The Vertex Cover Algorithm, 2006, http://www. dharwadker. org/vertex_cover [7] Ashay Dharwadker, The Vertex Coloring Algorithm, 2006, http://www. dharwadker. org/vertex_coloring [8] Ashay Dharwadker, A New Proof of The Four Colour Theorem, 2000, http://www. dharwadker. org [9] Ashay Dharwadker, A New Algorithm for finding Hamiltonian Circuits, 2004, http://www. dharwadker. org/hamilton [10] L. Euler, Solution d’une question curieuse qui ne paroit soumise a aucune analyse, Memoires de l’Academie Royale des Sciences et Belles Lettres de Berlin, Annee 1759 15, 310-337, 1766. 11] Eric Filiol, Edouard Franc, Alessandro Gubbioli, Benoit Moquet and Guillaume Roblot, Combinatorial Optimisation of Worm Propagation on an Unknown Network, Proc. [12] K. Heinrich and P. Horak, Euler’s theorem, Am. Math. Monthly, Vol. 101 (1994) 260. [13] R. M. Karp, Reducibility among combinatorial problems, [14] D. Konig, Theorie der endlichen und unendlichen graphen, Akademische Verlagsgesllschaft, Leipzing (1936), reprinted by Chelsea, New York (1950). [15] G. Lancia, V. Afna, S. Istrail, L. Lippert, and R. Schwartz, SNPs Problems, Complexity and Algorithms, ESA 2002, LNCS 2161, pp. 182-193, 2001.

Springer-Verlag 2001. [16] L. Lovasz, L. Pyber, D. J. A. Welsh and G. M. Ziegler, Combinatorics in pure mathematics, in Handbook of Combinatorics, Elsevier Sciences B. V. , Amsterdam (1996). [17] H. J. R. Murray, A History of Chess, Oxford University Press, 1913. [18] Shariefuddin Pirzada and Ashay Dharwadker, Graph Theory, Orient Longman and Universities Press of India, 2007. [19] F. S. Roberts, Graph theory and its applications to the problems of society [20] J. P. Serre, Groupes Discretes, Extrait de I’Annuaire du College de France, Paris (1970). [21] R. Thomas, A combinatorial construction of a non-measurable set,