Application of graph theory

  • 28 дек. 2010 г.
  • 1241 Слова
Applications of GRAPH THEORY
Abstract
The field of mathematics plays vital role in various fields. One of the important areas in mathematics is graph theory which is used in structural models. This structural arrangements of various objects or technologies lead to new inventions and modifications in the existing environment for enhancement in those fields. The field graph theory started itsjourney from the problem of Koinsberg bridge in 1735. This paper gives an overview of the applications of graph theory in heterogeneous fields to some extent but mainly focuses on the computer science applications that uses graph theoretical concepts. Various papers based on graph theory have been studied related to scheduling concepts, computer science applications and an overview has beenpresented here.
Introduction
Graph theoretical ideas are highly utilized by computer science applications. Especially in research areas of computer science such data mining, image segmentation, clustering, image capturing, networking etc., For example a data structure can be designed in the form of tree which in turn utilized vertices and edges. Similarly modeling of network topologies can be doneusing 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. This leads to the development of new algorithms and new theorems that can be used in tremendousapplications.

Applications of Graph theory
Graph theoretical concepts are widely used to study and model various applications, in different areas. They include, study of molecules, construction of bonds in chemistry and the study of atoms. Similarly, graph theory is used in sociology for example to measure actors prestige or to explore diffusion mechanisms.
Graph theory is used in biology andconservation 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. Forexample, 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 applicationsof 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).
Next, Game theory is applied to the problems in engineering, economics and war science to find optimal way to perform certain tasks in competitive environments. To represent the method of finite game a digraph isused. Here, the vertices represent the positions and the edges represent the moves.
Algorithms and graph theory
The major role of graph theory in computer applications is the development of graph algorithms. Numerous algorithms are used to solve problems that are modeled in the form of graphs. These algorithms are used to solve the
graph theoretical concepts which intern used to solve thecorresponding computer science application problems.
Some algorithms are as follows:
1. Shortest path algorithm in a network
2. Finding a minimum spanning tree
3. Finding graph planarity
4. Algorithms to find adjacency matrices
5. Algorithms to find the connectedness
6. Algorithms to find the cycles in a graph
7. Algorithms for searching an element in a data...
tracking img