Graph Theory
Applications of Graph Theory in Real Life
Sharathkumar.A,
Final year, Dept of CSE,
Anna University, Villupuram
Email: kingsharath92@gmail.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
Sharathkumar.A,
Final year, Dept of CSE,
Anna University, Villupuram
Email: kingsharath92@gmail.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
References: Ashay Dharwadker, The Vertex Coloring Algorithm, 2006, http://www.dharwadker.org/vertex_coloring 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, Mémoires de l 'Académie Royale des Sciences et Belles Lettres de Berlin, Année 1759 15, 310-337, 1766. [12] K. Heinrich and P. Horak, Euler’s theorem, Am. Math. Monthly, Vol. 101 (1994) 260. Leipzing (1936), reprinted by Chelsea, New York (1950). [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.