Some aspects of Graph Theory and It's Applications an Overview

I. INTRODUCTION

This paper has been divided into two sections. First section gives the historical background of graph theory and Second section emphasizes how graph theory is utilized in various fields. In mathematics graph theory is the study of graphs. A graph in this context is made up of vertices, nodes, or points which are connected by edges, arcs, or lines. A graph is a pair G = (V, E); where V is the set of all vertices and E the set of all edges; and the elements of E are subsets of V containing exactly 2 elements‟ is called a labeled graph if each edge e=UV is given the value f(UV) = f (u)*f (v), where * is a binary operation. In literature one can find * to be either addition, multiplication, modulo addition or absolute difference, modulo subtraction or symmetric difference. Graph play an important role in many areas like operational research, chemistry to genetics and linguistics, electrical engineering, geography to sociology, computer science and architecture. Graph theoretical ideas are highly utilized by computer science applications. Graph play an important role in mathematics for solving various typical problem like Bridges Königsberg, Travelling salesman problem, four colour theorem.

The graph theory started with the problem of Königsberg Bridge, in 1735. This problem lead to the concept of Eulerian Graph. Euler's formula relating the number of edges, vertices, and faces of a convex polyhedron was studied and generalized by Cauchy and L'Huillier, and represents the beginning of the branch of mathematics known as topology. Euler studied the problem of Konigsberg bridgeand constructed a structure to solve the problem called Eulerian graph. In 1840, A.F Mobius gave the idea of complete graph and bipartite graph and Kuratowski proved that they are planar by means of recreational problems. The concept of tree, (a connected graph without cycles was implemented by Gustav Kirchhoff in 1845, and he employed graph theoretical ideas in the calculation of currents in electrical networks or circuits. In 1852, Thomas Guthrie found the famous four color problem. Then in 1856, Thomas. P. Kirkman and William Hamilton studied cycles on polyhedral and invented the concept called Hamiltonian graph by studying trips that visited certain sites exactly once. In 1913, H.Dudeney mentioned a puzzle problem. Even though the four color problem was invented it was solved only after a century by Kenneth Apple and Wolfgang Haken. This time is considered as the birth of Graph Theory.

Graph theory is widely used to study for various applications in different areas. Graph theory is also used in geography used for geographical purposes like for measuring the speed of earthquakes. Graph theory is helpful in various practical problems solving in circuit or network analysis and data structure. It leads to graph practically not possible to analyze without the aid of computer. In electrical engineering the word is used for edge, node for vertex and loop for circuit. An electrical network is the set of electronic components i.e. resistors, inductors and capacitors etc. They include study of construction of bonds in chemistry and the study of atoms. biology and conservation efforts where a vertex represents regions where certain species exist and the edges represent migration path or movement between the regions. This information is important when looking at breeding patterns or tracking the spread of disease, parasites and to study the impact of migration that affect other species. Graph theoretical concepts are widely used in Operations Research. For example, the traveling salesman problem, the shortest spanning tree in a weighted graph, obtaining an optimal match of jobs and men and locating the shortest path between two vertices in a graph. It is also used in modeling transport networks, activity networks and theory of games. The network activity is used to solve large number of combinatorial problems. The most popular and successful applications of networks in OR is the planning and scheduling of large complicated projects. The best well known problems are PERT (Project Evaluation Review Technique) and CPM (Critical Path Method). Graph theory is also used in engineering, economics and war science to find optimal way to perform certain tasks in competitive environments.

In mathematics graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices, nodes, or points which are connected by edges, arcs, or lines. A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another. Here we discuss some problem related to graph theory-

The Seven Bridges of Königsberg is a historically notable problem in mathematics. This story is about the Swiss mathematician Leonhard Euler(1707- Königsberg is divided into four parts by the river Pregel and connected by seven bridges. It is possible to tour Königsberg along a path that crosses every bridge once, and at most once? You can start and finish when you want, not necessary in the same place. Trying various path quickly suggest that it is impossible, you always end with a bridge you have not crossed, but no way to get there without crossing another bridge twice. It would take more time for solving. But we solve this problem using graph theory. We make a graph of Königsberg problem like this and solve them using drawing graph like this-

Solution-Euler walks are possible if exactly zero or two nodes have an odd number of edges. If we have 2 nodes with an odd number of edges, the walk must begin at one such node and end at the other. Since there are only 4 nodes in the puzzle, the solution is simple. The walk desired must begin at the blue node and end at the orange node. Thus, a new edge is drawn between the other two nodes. Since they each formerly had an odd number of edges, they must now have an even number of edges, fulfilling all conditions. This is a change in parity from an odd to even degree.

chemical compounds. In computational biochemistry some sequences of cell samples have to be excluded to resolve the conflicts between two sequences. This is modeled in the form of graph where the vertices represent the sequences in the sample. An edge will be drawn between two vertices if and only if there is a conflict between the corresponding sequences. The aim is to remove possible vertices, (sequences) to eliminate all conflicts. In brief, graph theory has its unique impact in various fields and is growing large now a days.

The Field of Graph Theory plays vital role in various fields. One of the important areas in graph theory is Graph Labeling used in many applications like coding, x-ray crystallography, radar astronomy, circuit design, communication network addressing, and data base management. Modeling of network topologies can be done using graph concepts. In the same way the most important concept of graph coloring is utilized in resource allocation, scheduling. Also, paths, walks and circuits in graph theory are used in tremendous applications say traveling salesman problem, database design concepts, resource networking.

Graph theory is use in various problems solving in circuit or network analysis. It leads to graph practically not possible to analyze without the aid of computer. In electrical engineering the word is used for edge, node for vertex and loop for circuit. An electrical network is the set of electronic components i.e. resistors, inductors and capacitors etc. A graph representation of electrical network in terms of line segments or arc called edges or branches and points called vertices or terminals. It is used in the analysis of the electronic circuit like this- Electronic circuit Now we make a graph of this circuit like this-

The main aim of this paper is to present the importance of graph theoretical ideas in various areas of compute applications for researches that they can use graph theoretical concepts for the research. In this research we focus on the application of graph theory in distinct areas. It must now clear that Graph theory is not only as a branch of mathematics but also as a systematic tools in various fields especially in computer and electrical engineering, chemistry, geography etc. I hope this paper give some information related to graph theory and its application in various field.

1. file:///C:/Users/sangwan/Downloads/ Graph%20Theory%20_%20World%20of %20Mathematics.htm 2. Adam Schenker, Mark Last, horst Banke, Abraham Andel (2007). ‖Clustering of Web documents using a graph model‖, Springer werlog, September 2007. 3. Wikipedia, Graph theory 4. file:///C:/Users/sangwan/Downloads/ Graph%20Theory%20_%20World%20of%20Mathematics.htm 5. S.G. Shrinivas et. al. (2010). International Journal of Engineering Science and Technology Vol. 2(9), pp. 4610-4621 6. http://world.mathigon.org/

Assistant Professor, Department of Mathematics, Govt. College, Baund Kalan, Charkhi Dadri-127306, Haryana, India