Discuss the application of graph theory in the field of application?
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 its journey 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 been presented here. Keywords: Bipartite graph, Ad-hoc networks, Geometric spanner, Median graph, Voronoi graph. 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 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. This leads to the development of new algorithms and new theorems that can be used in tremendous applications. This paper has been divided into two sections. First section gives the historical background of graph theory and some applications in scheduling. Second section emphasizes how graph theory is utilized in various computer applications 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 the corresponding 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 structure (DFS, BFS) and so on. Various computer languages are used to support the graph theory concepts. The main goal of such languages is to enable the user to formulate operations on graphs in a compact and natural manner Some graph theoretic languages are 1. SPANTREE To find a spanning tree in the given graph. 2. GTPL Graph Theoretic Language 3. GASP Graph Algorithm Software Package 4. HINT Extension of LISP 5. GRASPE Extension of LISP 6. IGTS Extension of FORTRAN 7. GEA Graphic Extended ALGOL (Extension of ALGOL) 8. AMBIT To manipulate digraphs 9. GIRL Graph Information Retrieval Language 10. FGRAAL FORTRAN Extended Graph Algorithmic Language . Use of graph enumeration techniques: Graph enumeration technique is used to identify the computerized chemical identification. The list of all distinct chemical structures will be generated based on the given chemical formula and the valence rules for any new substance. To identify the chemical compounds automatically, a computer language called DENDRAL has been developed. Graph Theory in OR: Graph theory is a very natural and powerful tool in combinatoric operations research. Some important OR problems that can be solved using graphs are given here. A network called transport network where a graph is used to model the transportation of commodity from one place to another. The objective is to maximize the flow or minimize the cost within the prescribed flow. The graph theoretic approach is found more efficient for these types of problems though they have more constraints . Graph Coloring: Graph coloring is one of the most important concepts in graph theory and is used in many real time applications in computer science. Various coloring methods are available and can be used on requirement basis. The proper coloring of a graph is the coloring of the vertices and edges with minimal number of colors such that no two vertices should have the same color. The minimum number of colors is called as the chromatic number and the graph is called properly colored graph . Proper vertex coloring with Chromatic number 3 Proper edge coloring with Chromatic number 3 Graph coloring techniques in scheduling: Here some scheduling problems that uses variants of graph coloring methodologies such as precoloring, list coloring, multi coloring, minimum sum coloring are given in brief. Job scheduling: Here the jobs are assumed as the vertices of the graph and there is an edge between two jobs if they cannot be executed simultaneously. There is a 1-1 correspondence between the feasible scheduling of the jobs and the coloring of the graph. Precoloring extension: In certain scheduling problems, the assignments of jobs are already decided. In such cases precoloring technique can be adopted. Here some vertices of the graph will have preassigned color and the precoloring problem has to be solved by extending the coloring of the vertices for the whole graph using minimum number of colors. [4]. List coloring: In list coloring problem, each vertex v has a list of available colors and we have to find a coloring where the color of each vertex is taken from the list of available colors. This list coloring can be used to model situations where a job can be processed only in certain time slots or can be processed only by certain machines.[4] Minimum sum coloring: In minimum sum coloring, the sum of the colors assigned to the vertices is minimal in the graph. The minimum sum coloring technique can be applied to the scheduling theory of minimizing the sum of completion times of the jobs. The multi color version of the problem can be used to model jobs with arbitrary lengths. Here, the finish time of a vertex is the largest color assigned to it and the sum of coloring is the sum of the finish time of the vertices. That is the sum of the finish times in a multi coloring is equal to the sum of completion times in the corresponding schedule. Map coloring and GSM mobile phone networks: Groups Special Mobile (GSM) is a mobile phone network where the geographical area of this network is divided into hexagonal regions or cells. Each cell has a communication tower which connects with mobile phones within the cell. All mobile phones connect to the GSM network by searching for cells in the neighbors. Since GSM operate only in four different frequency ranges, it is clear by the concept of graph theory that only four colors can be used to color the cellular regions. These four different colors are used for proper coloring of the regions. Therefore, the vertex coloring algorithm may be used to assign at most four different frequencies for any GSM mobile phone network. The authors have given the concept as follows: Given a map drawn on the plane or on the surface of a sphere, the four color theorem assets that it is always possible to color the regions of a map properly using at most four distinct colors such that no two adjacent regions are assigned the same color. Now, a dual graph is constructed by putting a vertex inside each region of the map and connect two distinct vertices by an edge iff their respective regions share a whole segment of their boundaries in common. Then proper coloring of the dual graph gives proper coloring of the original map. Since, coloring the regions of a planar graph G is equivalent to coloring the vertices of its dual graph and vice versa. By coloring the map regions using four color theorem, the four frequencies can be assigned to the regions accordingly.