Forewords
Discrete mathematics discovers its applications in the contemporary era of computer science. Every component of discrete mathematics is extensity used in computer science. In this reflective paper, graph theory will be focused in the context of its applications. A graph is a modeling tool or set of relationships and technically stating it is a set of vertices and edges in which the graph theory is used as a modeling tool to study the network designs, communications and structure designs.
Graph theory ideas are extensity utilized in computer science. It helps in a different area of research as image segmentation,data mining, clustering, image capturing-, water marking, networking, data structure, and so forth. Data structure is the most initial subject that has been taught in preliminary courses of computer science. This can be designed in the form of the tree and using the edges and vertices of a graph. In a similar way, the modeling of network topologies can be done using concepts of graph theory. Graph coloring is most commonly used in many operating system concepts including resource allocation, scheduling and so forth.
History of Graph Theory
The graph theory was originated in year 1735 with the problem of Koinsber Bridge. This problem paved the path towards Eulerian Graph. Euler analyzed the problem of Koinsber Bridge and constructed structures for its solution called Eulerian Graph. Mobius gave the idea of complete graphs and bipartite graph in the year 1840. Gustav Kirchhoff introduced tree concept in 1845, and he also utilized theoretical graph ideas in the calculations of currents in electrical circuits. Thomas Gutherie in 1852 found the four color problem followed by Hamiltonian graph that was introduced by Kirkman and Hamilton. The term "Graph" was introduced in 1878 by Sylvester and later on the four color problem was solved by Heinrich using concepts of discrete mathematics.This was a time when the computer is largely used to solve major discrete mathematics problems especially the graph theory (Pirzada .& Dharwadker,2007; Shirinivas, Vetrivel, & Elango, 2010).
Graph Theory Applications
The theoretical study of graph theory has broad applications in chemistry especially in the study of molecules, construction of bonds, and they study of atoms. It is also having significant role in sociology in order to measure the actors’ prestige or to explore the diffusion mechanism. It has its application in biology for conservation efforts where a vertex represents regions for certain existing species, and the edges represent migration paths between the regions. Graph theory is widely used in operational research as the shortest spanning tree, the traveling salesman problem, in a weighted graph, finding an optimal match of jobs and men locating the shortest path between two different vertices in the graph. It is providing modeling transport network, the games theory and other activity networks. Consequently graph theory plays an important role in many different areas of life.
Computer Science & Graph Theory
Graph theory is mostly used in computer science in developing graph algorithms. Various algorithms are used to solve problems that require modeling in the form of graphs. These algorithms are used to solve the theoretical concepts of graphs which are then used to solve the corresponding computer science application problems (Shirinivas et al., 2010). Some of the algorithms that are derived from the graph theory include:
- Shortest Path Algorithm
- Finding Minimum Spanning Tree
- Finding Graph Planarity
- Finding Adjacency Matrices
- Finding the correctness
- Finding the Cycles in the Graph (Operating system: Deadlock concept)
- Searching for an Element in a Data structure
Computer science involves in various languages to support the theory of graph. The main goal of those computer languages is to facilitate the user to formulate operations on graphs in a very natural manner. Some of those languages are:
- Sspanning tree in the graph(SPANTREE)
- Graph Theoretic Language (GTPL)
- Graph Algorithm Software Package (GASP)
- Extension of LISP (List Processing)
- Extension of LISP
- Extension of FORTRAN
- Graphic Extended ALGOL (Extension of ALGOL)
- Graph Information Retrieval Language (GIRL)
- FORTRAN Extended Graph Algorithm Language (Pirzada. & Dharwadker, 2007; Shirinivas, et al., 2010).
Graph Enumeration Technique
Graph enumeration technique has been developed that is used chemical identification. Based on given formula, it generates all distinct chemical structures and the variance rule for any new substance. DENDRAL is commonly used for this purpose to overcome the issues (Shirinivas et al., 2010).
Graph theory is used as a powerful tool in combinatorial operations research. Some OR problems are solved by graph theory including transport network where a graph is used to model the transportation of the commodity from place to place with the intention to maximize the flow and minimize the cost within the described flow (Liu et al., 2008; Pal, Sarma, & Ray,2007).
Graph coloring is used in many real time applications of computer science and is most commonly used concept of graph theory. It offers various coloring methods that can be used as per requirement. In order to color the graph properly, it is required to color the vertices of the graph and edges with a minimal number of colors so that two vertices cannot have the same color. The minimum number of color scheme that is used is known as chromatic number, and the corresponding graph is called properly colored graph (Pirzada. & Dharwadker, 2007; Shirinivas et al., 2010).
According to Pau et al.,(2007) , in a given set of jobs that need to be assigned to time slots, where each job requires one time slot and jobs can be scheduled in any order. He pointed out that share a resource in case the pair of jobs conflict, it cannot occur at the same time. The corresponding graph contains a vertex for each job and edge for each conflicting pair. The chromatic number of this graph gives the minimum times required to finish all jobs without conflict. Operating system resource sharing and deadlock handling is managed using graph theory, and it is also simulated using the graph theory.
Various scheduling problems are modeled using graph coloring technique that include job scheduling, pre coloring the extension, aircraft scheduling, bi-processor tasks, list of coloring, minimum sum coloring, job shop scheduling problems, timetable scheduling and so forth.
Mobile phone network as Groups Special Mobile known as GSM is used divide geographical area into hexagonal regions or cells. Each cell has a communications tower that directly communicates with the mobile phones in that cell or region (Phukon, 2012). The mobile phones are used to connect to the GSM network by searching for cell in neighboring region of one goes out of his region. GSM operates only in four different frequency ranges, so only four coloring scheme from graph theory can be used to color the cellular region of GSM network. Given a map drawn on a plane or sphere, the four color theorem can be used to color the regions of the map with optimum use of four distinct colors by avoiding the same color for two adjacent regions. A dual graph can be constructed by putting a vertex inside in each region and connecting two vertices by edge off their respective regions and sharing a whole segment in their common boundaries. In this way, proper coloring of the graph provides proper color to the original map. Thus, using four coloring theorem of the graph theory, the four frequencies can be assigned to different regions accordingly (Pirzada & Dharwadker, 2007).
Computers are often connected with one another in order to interchange information. There are some issues in ad hoc network as connectivity, scalability, routing, and modeling and computer simulation. This network is formulated as model for a graph in order to use the model for analyzing these issues. Graphs are algebraically represented here as matrices and network can be automated with the help of algorithms. Various algorithms are also available for finding out the congestion in MANET’s where such networks are modeled based on graph theory. It helps a lot in finding the nearest path home using GPRS device (Dickinson, Ramin & Zabih, 2001).
It is a fact that mathematics of modern computer science is built on discrete mathematics particularly combinatorics and graph theory. So in order to learn the fundamental algorithms used by computer programmers, one must have a solid background in discrete mathematics.
Domination is another graph parameter but this concept is relatively new. It works in such a way that we want to know the smallest number of vertices in our graph, so we have to choose a vertex in a manner that it is adjacent to one of the vertices we picked. It is like a committee choice; we want to select a committee and we know who the representation is. The application of domination is in transportation networks, distribution logistics, and an alarm location in facilities, radio, and TV communication tower location (Shirinivas et al., 2010).
Graph theory also helps in simulated computer games. The method of finite game is represented by digraph that is normally used where the vertices represent the positions and edges represent the moves. This Game Theory is applied to the problems in engineering, economics and war science in order to find the optimal way to perform certain tasks in competitive environments.
The efficient applications of games admit declines to parity games over larger game graphs. This is not simply a case for games modeling reactive devices, with triumphing problems pointed out in some temporal reasoning or dialogic over endless courses for Muller games. Further, games arise as the model-checking games for fixed-point logic such as the modal LFP, the extension of first-order reasoning by the very least and biggest fixed-points (Canavoi, Grädel & Rabinovich, 2014).
Problem from Graph Chapter
We will solve and show that a finite graph is connected if and only when it has a spanning tree. Consider, G be a connected graph and the set “S” of all trees T⊂G that are ordered in a pair by the subgraph relation. By application of Zorn’s Lemma, it must be made sure that every chain “C” has an upper bound, it means that a tree containing every T∈C as a subgraph. Now one can make a claim that T* = UC ( This is like a tree).
It is obvious that T is a subgraph of T* for every T∈C by construction. The main part that need to be verified that T* is a tree. Let’s consider, that T* is not a tree. Then it might be either T* is disconnected, or it has a cycle. In the case, T* is disconnected, then there are two possible vertices u, v ∈ T* that are not connected with a path in "T" and u ∈ Tu for some Tu ∈ C and v ∈ Tv for some Tv ∈ C and C is a chain so either Tu ⊂ Tv or Tv ⊂ Tu. In either case, u is supposed to be connected to "v" with a path in the larger trees, and "T"* in return contains this path that is a contradiction. This contradiction to T* containing a cycle is similar in a way that all edges present in a specific cycle should appear somewhere in the chain, and one of the supposed tree in the chain is not acyclic. Since every chain has an upper bound as said above, so S has a maximal element by Zorn's Lemma. It is easy to see that it must be a spanning tree.It has many applications especially in finding the shortest path. Dijsktra Algorithm used the above mentioned proof in order to prove the shortest path in the graph. This algorithm is most famous in computer science to obtain the shortest paths in the graph.
Conclusion
Applications of graph theory and the modern computer science has been rotating around graph theory concepts and ideas. It is considered as the vital course for computer science professionals and students. Students start learning applications of graph theory in data structures by solving and applying different simple to hard algorithms using graphs and trees. It even helps in modeling of queues and linked lists problems along with helping in all the sorting algorithms. The shortest path algorithm is the most common algorithm students use to find out the shortest path in a tree or graph. Shortest path algorithm has two forms of application called as breadth first search algorithm and depth first search algorithm. Even the densest graph or tree can be evaluated using any of the shortest path algorithms. Discrete mathematics along with computer science has applications in the rest of the domains including the special application in chemistry, physics and biology and rest of the social science areas.Many researches are under consideration to find out the further applications of discrete mathematics in modern computer science. The day to day problems can be solved in relatively efficient manner and innovations can be made using graph theory and computer science. This subject is considered very important for teaching computer science, and it is being said by the researchers that if someone wants to excel in computer science, he/she needs to be the discrete mathematics genius. Many problems related to modem telecommunications and networks would not have been possible without reinforcements and invention of discrete mathematics. This integration of discrete mathematics into computer science is the success of the millennium that has revolutionized the computer world and even the most complex problems are now being solved using discrete mathematics theoretical concepts and ideas.
Researchers rely on the concepts of theoretical discrete mathematics in order to prove or disprove any new concept in computer science as it is a normal norm to assess the new concept statically before going for real simulation of a computer system. Those statistical evaluations are normally performed using discrete mathematics concepts. Research is going on both in discrete mathematics as well as its applications in computer science. The revolution can be seen in the computer world, and more it is a contribution to the discrete mathematics as it provides the basis for the authentication of any new concept. This is the simplest form of mathematics that is being relied upon by computer scientists for many years.
References
Canavoi, F., Rabinovich, R. & Grädel, E.,(January 28,2014). A discrete strategy improvement of the algorithm for parity games & complexity measures for directed graphs. Theoretical Computer Science. Retrieved from: http://science/article/pii/S0304397514000024
Dickinson, S. Pelillo, R. & Zabih, R. (2001). Introduction to the special sections on graph algorithm in computer vision, Transaction on pattern analysis and Machine Intelligence, 23(10), 1049-1052.
Hong, H.G. & Song, H.Y. (2010). Analysis and design of unified – Hardware abstraction layer to support various multimedia – SoC with Android platform. Int. Jr. of Multimedia and Ubiquitous Engineering, 7 (2), 365-370.
Liu, B.H, Ke W.C., Tsai, M. & Tsai, C. (2008). Constructing a message – pruning tree with minimum costs for tracking moving – objects in wireless sensor – network, NP-complete and an enhanced data aggregation structures, Computers 57(6), 849-863.
Pal, J.A, Ray, B. & Sarma, S.S. (2007). CCTP – Graph Coloring algorithms – Soft computing Solutions, Cognitive Informatics, 364-372.
Phukon, K.K.(2012).A Composite Graph Model for Web documents and the MCS –technique, Int. Jr.of Multimedia and Ubiquitous Engineering, 7(1), 45-51.
Pirzada, S. & Dharwadker, A. (2007). Applications of graph theory, Journal of the Korean Society for Industrial and applied Mathematics, 11(4).19-38.
Shirinivas, S.G., Vetrivel, S. & Elango, N.M. (2010). Applications of graph theory in computer sciences – an overview, Int. Jr. of Engineering Science and Technology,2(9), 4610-4621.Retrieved from: http://www.cs.xu.edu/csci390/12s/IJEST10-02-09-124.pdf
