Graph Theory: Research Paper

Research paper, Pages 9 (2174 words)

Views

552

The discipline of mathematics is an expansive subject, because of this, its applications permeate throughout various fields of study. One particular branch of mathematics that performs a pivotal role in computer science is graph theory. Graph theory implements a unique approach to solving complex problems using structural based models that have bolstered many advances within the realm of computer science. This paper will examine graph theory's basic elements such as its origins and definitions of various structural modes that have played a pivotal role in its development.

Don't use plagiarized sources. Get your custom essay on

“ Graph Theory: Research Paper ”

Get custom paper

NEW! smart matching with writer

Before graph theory's implementation as a branch of mathematics, its elemental structure existed within many recreational math problems that were solved to satisfy one's curiosity. In 1735, solving various mathematical problems as a means of entertainment met its eventual evolution via the "Seven Bridges of K?nigsberg" and Leonhard Euler. The mayor of Danzig, Carl Leonard Ehler drafted a letter to Leonard Euler to implore his help in solving a curiosity that arose from the city's residences (Benjamin, Chartrand, & Zhang, 2017, p.

92).

To provide some context behind the letter, Benjamin, Chartrand, & Zhang, stated that "many of the citizens of K?nigsberg spent their Sunday afternoons strolling about the city. The problem arose as to whether it was possible to walk about the city and cross each of the seven bridges exactly once" i.e., figure 1 (Benjamin, Chartrand, & Zhang, 2017, p. 93).

Leonard Euler's response to the mayor expressed that he did not consider this problem to be of any importance in mathematics and could be solved by reason alone.

He theorized that the geometry of position previously proposed by Leibniz and Wolff can be applied, yet, he was ignorant of its workings. In spite of his limited knowledge on the geometry of position Leonard Euler presented the first solution via his paper originally written in Latin "Solutio problematis ad geometriam situs pertinentis'' ("The Solution to a Problem Relating to the Geometry of Position'') to the Seven Bridges of K?nigsberg problem to the Petersburg Academy in 1735 (Benjamin, Chartrand, & Zhang, 2017, p. 95).

Euler expressed that if there were five bridges going to or leaving from solid ground, and the solid ground was labeled as A, either an individual is starting at A or ending at A. Label A will appear 3 times in the route and since there are three bridges with the labels B, C and D respectfully. B, C, and D bridges will appear twice in each route, equaling nine terms and not eight, implying a contradiction i.e., figure 2 (Benjamin, Chartrand, & Zhang, 2017, p. 97). Leonard Euler proved that it was impossible to cross the K?nigsberg Bridge only once. Beginning as a mathematical curiosity, the Seven Bridges of K?nigsberg problem presented by the mayor of Danzig and solved by Leonard Euler presented to people a new method of solving complex problems.

What is a graph? Benjamin, Chartrand, and Zhang writes "The mathematical structure known as a graph has the valuable feature of helping us to visualize, to analyze, to generalize a situation or problem we may encounter and, in many cases, assisting us to understand it better and possibly find a solution" (Benjamin, Chartrand, & Zhang, 2017, p.1). They introduce us to a simplified understanding of the concepts within graph theory. The authors introduce various puzzles and games such as The Problem of the Five Princes, The Three Houses and Three Utilities Problem, and the Job Hunters Problem which provides the reader with practical examples to solve to enhance learning. For some context, let's consider The Problem of the Five Princes and the methods involved to solve this complex puzzle.

The story describes a kingdom, a king, and five princes, they present the audience with a hypothetical problem. The king wants to ensure that after his death, his kingdom is separated in five sectors, one sector for each prince and each sector should have a common border, i.e., figure 3 (Benjamin, Chartrand, & Zhang, 2017, p.1). People are instructed to place a point in each sector then connect the sector with a line, therefore if these sectors contain these points, there is a shared border (Benjamin, Chartrand, & Zhang, 2017, p.1). The explanation above using the terminology "points" and "lines" are prime examples of elements that make of a graph. For a more formal explanation, a graph is a collection of points which are referred to as vertices and the lines connecting each sector are called edges (Benjamin, Chartrand, & Zhang, 2017, p.1).

Chartrand & Lesniak provides to the reader with an in-depth study into graph theory that outlines the basic concepts of graphs along with the different forms used. i.e., figure 4. Chartrand & Lesniak introduce the reader to the basic structural properties of a graph such as cut-vertices, bridges, and blocks and the symmetry involved. The students are given an example of cut-vertices which are disconnected graphs by removing one vertex or an edge (Chartrand & Lesniak, 1996, p.33). Chartrand & Lesniak gives an explanation of an cut-vertex through theorem 2.1 that states "A vertex v of a connected graph G is a cut-vertex of G if and only if there exist vertices u and w (u, w =1= v) such that v is on every u-w path of G" (Chartrand & Lesniak, 1996, p.33) i.e., figure 5.

The in-depth explanation of graphs and digraphs provided by Chartrand & Lesniak will expand the readers' prior understanding of graph theory using theorems and proofs. The advanced graph theory concept of map colorings provides proof that any map on a plane or sphere can be colored with four or fewer colors. Vertex colorings derives for the Four-Color Problem, coloring of a supposed graph G by assigning colors to a set of vertices located on graph G. Each vertex is colored with one color and every adjacent vertex is colored with a different color. i.e., figure 6.

Although graph theory was implemented to provide a visual structural model to solve complex problems in a simplified manner, the underlying theorems behind the numerous graphs can be difficult to grasp. Hazzan & Hadar provide the reader with the intent of their research by stating that "This article presents research on students' understanding of basic concepts in Graph Theory. Students' understanding is analyzed through the lens of the theoretical framework of reducing abstraction" (Hazzan, O., & Hadar, I., 2005, p.1). Their intent is to simplify the concept of graph theory due to the importance of the subject to computer science students. By focusing on the basic definitions, the various graphs included, along with their attributes such as binary trees and spanning trees, the students are provided a framework to understand the overall concept of the theory. Reducing the complexities of graph theory by applying a constructivism cognitive theory approach allows a gradual understanding to form and take shape.

In the Book of Trees: Visualizing Branches of Knowledge, the author Manuel Lima provides the reader with a detailed description of the origins of trees from a historical, artistic, religious and mathematical point of view. Throughout the book, they introduce the reader to the Tree of Life from Kabbalism, Yggdrasil tree, the Tablet of the cross and the Bodhi tree. As for the mathematical perspective, Manuel Lima gives the reader figurative, vertical, horizontal, multidirectional, and radial trees.

A Plan of Organization of New York and the Erie Railroad diagram from 1855 provides the reader with an organizational structure based on a functional tree. In the year of 1866, Ernst Haeckel implements a diagram called The Family Tree of Mammals from Generelle Morphologie der Organismen based on the evolutionary ideas of Charles Darwin. The reader is given a well-rounded understanding of trees in more of an observational approach, yet the core of the information is presented effectively.

Rahman and Kaykobad begin by providing the reader with a definition of the Hamiltonian cycle. In this paper, the authors present theorems stating sufficient conditions for a graph to possess Hamiltonian cycles and Hamiltonian paths. The authors explain why the theorems are important and detail famous Ore's theorem that follows from the result of their research findings. Proof of Ore's theorem states that if G as a simple graph with n vertices with such that degree (u) + degree (v) for every set of nonadjacent vertices u and v in graph G, then G has a Hamiltonian circuit (Rahman, M. S., & Kaykobad, M., 2005, p. 258). i.e. figure 7. The concepts implemented provides the reader with examples of Hamiltonian cycles and paths in practice.

A branch of graph theory that has been inserted into multiple industries from networking, finance, and geology is topology. Topology is the discipline that study geometric properties of two objects to compare the equivalence after transformation such as stretching, bending, twisting and shrinking. Sanderson, Peacock, Nixon, and Rotevatn, in their analysis of fracture networks, introduces the reader to fracture networks beginning the mineral mining treatise of Georgius Argicola written in 1558. According to the article, "His amazing woodcuts show these vein networks as they intersect the surface and also his 33 three- dimensional interpretation in the sub-surface. He proposed that veins both bifurcate and 34 cross-cut one another, noting their relative position and inferred age rather than presenting 35 details of their size and orientation" (Sanderson, Peacock, Nixon, and Rotevatn, 2018).

Further, along with the research paper, the authors provide a classification of networks using topology, a branch of graph theory. According to the authors, "Topology describes the relationship between fractures and, as such, adds information for the characterization of a network" (Sanderson, Peacock, Nixon, and Rotevatn, 2018). The practical approach research by the authors gives the reader a glimpse into the implementation of a topological classification of fracture networks.

Raymond F. Tennant makes the connection in his research work between planar graphs and abstract algebra ideas of Platonic and Archimedean solids. "A graph is called planar if it can be drawn in the plane in such a way so that no two edges meet each other except at a vertex to which they both connect. The regions bounded edges are called faces" (Tennant, 2000). We are introduced to the concept of the duality that exists in a polyhedral that can be understood using a sequence of graphs. "If P is a connected planar graph and p* then the dual graph of P, call it P*, can be constructed from P in the following manner. First, choose one point inside each face, including the face of infinity, of the planar drawing of P. These points are the vertices of P*. Next, for each edge of P, draw a line connecting the vertices of P* which lie on each side of the edge. These new lines are the edges of P*" (Tennant, 2000).

Graph theory has helped advance computer scientist's understanding of previously defined models such as the world wide web by combining directed graphs with machine learning. Zhou, D., Huang, J., & Sch?lkopf, B., in this research paper propose using directed graphs as a general framework for learning from labeled and unlabeled data. "Given a directed graph, the vertices in a subset of the graph are labeled. Our problem is to classify the remaining unlabeled vertices. Typical examples of this kind are web page categorization based on hyperlink structure and document classification based on citation graphs" (Zhou, D., Huang, J., & Sch?lkopf, B., 2005).

Zhou, D., Huang, J., & Sch?lkopf, B., begin to define Google's page rank algorithm "PageRank is based on a direct recursion as follows: an authoritative web page is one that receives many links from other authoritative web pages. When the underlying graph is undirected, the approach that we will present reduces to the method of Zhou et al" (Zhou, Huang, & Sch?lkopf, 2005). Applying a directed graph to the worldwide web then defining web pages as vertices and directed edges as hyperlinks with given weights strengthen the classification of pages into multiple categories.

. In 283 years since Leonard Euler's solution to the Seven Bridges of K?nigsberg, we still see the influence of graph theory in computer science applications such as Google search engine, Google Maps, Wi-Fi networks, and location-based advertising. From geometry of position to graph theory this visual based structural model has proven to be an effective branch of mathematics.

References

Benjamin, A., Chartrand, G., & Zhang, P. (2017). The fascinating world of graph theory Princeton, NJ: Princeton University Press.

Chartrand, G., & Lesniak, L. (1996). Graphs & digraphs (3rd ed.). London, UK: Chapman & Hall.

Hazzan, O., & Hadar, I. (2005). Reducing abstraction when learning graph theory., 24(3).

Lima, M. (2014). The book of trees: Visualizing branches of knowledge. New York: NY

Princeton Architectural Press.

Rahman, M. S., & Kaykobad, M. (2005). On Hamiltonian cycles and Hamiltonian paths. Information Processing Letters, 94(1), 37-41. doi: 10.1016/j.ipl.2004.12.002

Sanderson, D.J., Peacock, D.C.P., Nixon, C.W., Rotevatn, A. (2018). Graph theory and the

analysis of fracture networks, Journal of Structural Geology, doi: 10.1016/ j.jsg.2018.04.011.

Tennant, R. (2000). Polyhedral models in group theory and graph theory. Sorbonne University Abu Dhabi. Paris: Research Gate.

Zhou, D., Huang, J., & Sch?lkopf, B. (2005, August). Learning from labeled and unlabeled data on a directed graph. In Proceedings of the 22nd international conference on Machine learning (pp. 1036-1043). ACM.