Graph Theory

# Graph Theory

GRAPH THEORY 1

The graph theory is one of the most applied theories in mathematicalproblems in the world today. The theory traces its roots to ancientGermany, where locals were trying to find a solution to crossing ariver that had seven bridges. From a historical perspective, thetheory has undergone significant developments every other centurysince its inception. There are notable mathematicians who haveadvanced logical explanations to help mathematicians solve graphissues. The mathematical application of the theory involves someconcepts, all which draw upon the initial methodologies that wereapplied by early scientists. In the real world, the graph theory isone of the most applied mathematical theories. It is used byinternational organizations, as well as leading businesses, insolving day-to-day problems. This paper provides an analysis of thehistory of the graph theory, its mathematics, and real-lifeapplication.

Historyof the graph theory

The earliest known source of the graph theory was in the city ofKonigsberg (Buckley &amp Lewinter, 2013). The city was formerlyfound in Germany. However, it is today located within the boundariesof Russia. The city had seven bridges. These bridges connected twoislands with the mainland. One of the main worries of the locals washow they could cross all the bridges at a go, without having totraverse each at a time.

Euler, a well-known mathematician, came up with a solution in 1746(Buckley &amp Lewinter, 2013). He came up with an idea of graphs,which would help the locals in their quest of crossing the river, asthey wanted. However, he told the locals that it was impossible forthem to cross all the rivers at one time as they wished. To provide asolution, he went back to the drawing board and came up with asolution in terms of the graph theory. The first solution was toeliminate all the unnecessary hindrances that would limit thetraversing. As such, he drew a picture that had dots. The dotsrepresented the landmasses while the lines represented the bridgesthat were found in different sections of the river. Below is theoutcome of the picture that Euler drew.

Figure1: Euler`s solution to the seven bridges of Konigsberg problem.

Euler’spicture solved the problem significantly. According to the theory hecame up with, the solution could be arrived at by drawing a linewithout lifting the pencil out of the paper. After giving the localpeople and other scholars a chance to do it, it was finally agreedthat it was an impossible fete. However, Euler’s experiment was notentirely a failure. It helped him to explain to the locals why thiswas not possible, and as such, explain the characteristics of theproblem that made it so challenging. It was during this that he cameup with the ‘degree of nodes’. These are the number of edges thattouch a certain node. The case of the bridge of Konisberg set theplatform for further studies in the theory of graphs. Using hisinitial experiments, Euler formulated elements of graphs, such asedges and vertices, which helped mathematicians after him to furtherthe concept further.

AfterEuler’s case of the seven bridges of Konisberg, there was littleprogress in the theory of graphs, not at least until after about acentury. Mathematicians, using Euler’s concept and elements of thegraph, focused on studying a particular class of graphs,mathematically known as the trees (Buckley &amp Lewinter, 2013).Trees are mathematical structures that are viewed as data structures.Cayley (1887) was the first mathematician to describe trees, where heproposed two views that mathematicians use up to date. The first oneis that trees are data structures. They contain elements that are themain connectors. Secondly, Cayley proposed that undirected paths inthe tree vertices are connected by exactly one path. The maincontribution of Cayley’s work on the graph theory was the creationof a database of trees of up to 18 vertices. This was in line withthe concept and thoughts of Euler’s work on the seven bridges ofKonisberg.

After these developments, Sylvester &amp Baker (2012) say that JamesSylvester introduced the term `graph` as applied in modernmathematics. In the publications by Sylvester made two majorexplanations. The first one was the Quantic invariants. In thiscontext, invariants are a binary form of coefficients of x and y. Thesecond one was co-variants. Co-variants are mainly used in physicsand statistics. These turned out to be major parts of the graphtheory as it is known and applied today. George Poyla made perhapsone of the greatest contribution to the graph theory in the 20thcentury (Poyla, Tarjan &amp Woods, 2013). Using the concepts ofCayley’s work, he wrote papers that addressed fundamentalgeneralizations of the graph theory. He fused the ideas of the graphtheory and spread them to other disciplines, most notably chemistry.

Whilethere are some publications that have shaped the graph theory, thefirst textbook was published in 1936. The author of this book was amathematician, Denes Konig. Konig was a renowned Hungarianmathematician whose contributions to the graph theory earned him apermanent spot in the history of mathematics. In his book, hedescribed an equivalence between the maximum matching problem and theminimum possible vertex on graphs. Besides being an independentdiscovery, he drew a lot from the works of earlier publishers. Hiswas the case of a generalized weighted graph. Another significant interms of a published book was one by Frank Harary (Harary, 2015).Mathematical scholars consider this nook as one of the mostcomprehensive in the field of graph theory.

Inthe modern history, mathematicians addressed issues in the graphtheory by approaches that are more technical. For instance, in the19602, Heinrich Heesch designed a methodology for solving graphsusing a computer (Jensen &amp Toft, 2011). The program usedfundamental elements known as ‘discharges’ to show the propertiesof graphs. However, given the complexity of the commands and littledevelopments in computer technology, the methodology was too complexto be adopted. Regardless, this was a milestone in the theory ofgraphs. In the modern application, graphs can be visually representedthrough manual and digital drawings.

Mathematicsof the graph theory

Basics

Harary (2013) argues that there are no standard notations for thegraph. This is because mathematicians view them as theoreticalobjects. There are notations and notions for defining finite sets.These sets denote the size of the graphs, that is, by defining thecardinality and number of elements. An example of a finite set is X.as such, |X| denote the size. Other basic elements in thetheory of graphs are the floor, ceiling, partition, Cartesian productand the symmetric difference (Harary, 2013). At the same time, thegraph theory has many examples of NP-complete problems. These have anefficient algorithm and solutions to it. When drawing graphs,mathematicians generalize loops and parallel edges between thevertices, and in the end, come up with a multi-graph. When using theplane figure to give visual representations, the mathematicians haveto program the figures in the form of matrices. Matrices are idealfor representation of graphs in computers.

Connectivityof Graphs

The concept of connectivity of graphs draws its basics from the firstever problems in graphs, which was the seven bridges of Konisberg.Mathematically, the connectivity of graphs is a concept thatspecifies the minimum number of elements that have to be used todisconnect nodes from each other. This concept is important for thecomputation of network flows, which are the modern form of thesolution to the seven bridges of Konisberg. One of the examples ofconnectivity is the vertex and edge connectivity. These, on a graph,are disconnected at 0. In a tree, connectivity is represented by thelocal edge connectivity between vertices that result in 1.Mathematically, the common forms of connectivity are the 2-connectedand 3-connected graphs. The diagram below represents an example ofconnectivity in the theory of graphs.

Figure2: The removal of the edge of disconnects the graph.

Toursand matching

There are three main concepts under tours and matching in theperspective of the theory of graphs. These are the Eulerian graphs,the Hamiltonian graphs, and Matchings. Under the Eulerian graphs, thefirst proper problem was the seven bridges of Konisberg problem.Under these, there are the Euler tours. A Euler tour is a trial of agraph line that visits every edge only once. It is denoted as W= e1e2….en.If G is not Eulerian, then the line has to pass every pointtwice. The graph below is a Eulerian graph that duplicates edges.

Figure3: Eulerian graph that duplicates edges

According to the Hamiltonian concept, a path if a graph isHamiltonian only of it visits a vertex of G only once.However, unlike the Eulerian graph, there is no good characterizationin the Hamiltonian graph. However, it has unique conditions thatdescribe it. Finally, the matching concept gives an availabilityrelation, where every element is uniquely matched with an availablecompanion.

Coloring

The three major concepts under coloring in graphs theory are edgecoloring, the Ramsey theory, and vertex coloring. An edge coloring ofedges and vertices are very useful, as they help mathematicians tocreate relationships between edges. Using chromatics, mathematicianslabel letter G as the main coloring property. The logic behindthis is the ‘properness’ in application to the edges and vertices(Burkley &amp Lewinter, 2013). The Ramsey theorem states that “Letalpha be an edge of G., a subgraph of H CG is (i-)monochromatic, if all edges of H have the same color TheRamsey theory addresses unavoidable patterns in combinations. Thetheory holds that each of the colorings of the edges K6contain 2 colors, which resulting a monochromatic triangle. Thirdly,the vertex coloring classifies graphs using colorings on a graph ofG. The colorings identify vertices with similar properties andaspects. Figure 4 shows an example of a 3-chromatic graph.

Figure4: 3-chromatic graph

Graphson surfaces

There are also three basic concepts that describe the theory ofgraphs from the perspective of graphs on surfaces. The first one,planar graphs, defines a graph that can be drawn on a plane, withouthaving any two edges intersecting. Planar graphs have fast algorithmsto test if the graph is truly planar or not. Auslander and Peter(1961) made a significant contribution to the description of planargraphs (Shilov &amp Silverman, 2012). The second concept of graphsin the surface is the coloring of planar graphs. The concept wasdesigned out of a 120-year old 4-color conjecture that was solved in1976 by mathematicians Appel and Haken (Chandran, 2015). The theorystates, “if G is a planar graph, then X (G) is equalto or less than 4.” The third concept of graphs on the surface isthe genus of a graph. According to the theory, a graph that can bedrawn without crossing edges is a planar graph.

Directed graphs

MathematicianHarary explains that in some relations, the relation between objectsis not symmetric. This is why mathematicians need directed graphs insuch situations. For directed graphs, the edges of the graph areoriented from one vertex to another. The diagram below shows anexample of a directed graph.

Figure 5: A directed graph

Theprescribed description of a directed graph is “a graph D =(VD, ED) consisting of vertices VD and directed edgesED without loops vv” (Sylvester&amp Baker, 2012). This is also known as a digraph. Secondly,there are network flows. These are networks that possess extrarequirements network flows problems were first described in the1950s by mathematician T.E. Harris (Harary, 2015).

Realworld application of the graph theory

Themost common applications of the graph theory in real-life traces itsroots back to the origin of the theory itself, which was crossing theseven bridges of Konisberg. In real life, the theory is used to findthe shortest path connecting two places. Here, the problem solverapplies the concepts of the theory to find the shortest path betweentwo given intersections. This can be moving from one house to anotheron a certain road, without having to pass through unnecessary pointsalong the path.

Anotherapplication of the theory of graphs is in electrical circuits. Forinstance, an electrician looks to have an electrical circuit goingthrough a wall that is made up of several layers. This means that theelectrical signal is attenuated when the connection travels throughthe materials of the wall. This is due to partial reflections andrelated technical issues. When this happens, there are issues overthe amount of energy that the electrical connection relays to thetransceiver at the end of the line. However, using the theory ofgraphs to solve this problem, the electrician can rephrase theproblem in terms of a directed weighted graph, as described earlier.Using this concept, the electrician can set vertices at the start,followed by intermediate layers through the path of travel. The finalpath can be computed by conducting a simple calculation of theweighted adjacency matrix.

Leadingcompanies have used the theory of graphs to solve some majortechnical issues affecting their operations. One of the famousexamples is the case of Amazon, a leading online retailer website.Using Google tool, the company perceived the internet as a giantgraph, which they had to solve. To link the sellers and the buyers,the company considered the algorithms of the graph that connectedthem. Every web page was treated as a node, and there had to edge tolink the modes. The underlying assumption was that the edges in theinternet graph that the company was considering had a definitedirection.

Inanother corporate application of the graph theory, Google used analgorithm known as PageRank to help it to link websites. Using the‘Heuritic algorithms’, the company’s engineers used TSPsolutions to link thousands of cities within a relatively short time(Osman &amp Kelly, 2012). However, there is no assurance that theexplanations work perfectly. However, what is known is that themethods of solving the graphs, especially Heuristics, providessolutions that are good enough to help the company serve its clientsoptimally.

Conclusion

The origin of the graph theory was quite interesting, given that itcame out of the need for people to solve a very basic problem. Whatbegan as a quest to traverse seven bridges with ease gave rise to oneof the most interesting theories in mathematics and science at large.Owing to the input by renowned mathematicians, such as Euler andothers that came after him, people can now find solutions to dailyproblems that touch on efficiency and effectiveness of paths. Thegraph theory remains to be one of the most widely researched areas inmathematics, with concepts and solution to problems related to thetheory coming up every day. The innovation of computer technologyimproved the way that mathematicians solved graph problems, which hashelped modern companies in running their day-to-day business.

References

Buckley, F. &amp Lewinter, M. (2013). Introductory graph theorywith applications. New York, NY: Waveland Press.

Chandran, D. L. S. (2015).Chvatal-s theorem, toughness, Hamiltonicity and 4-colorconjecture.&nbspGraphTheory.

Harary, F. (Ed.). (2015).&nbspAseminar on graph theory.Courier Dover Publications.

Jensen, T. R., &amp Toft, B.(2011).&nbspGraphcoloring problems&nbsp(Vol.39). John Wiley &amp Sons.

Osman, I. H., &amp Kelly, J. P.(Eds.). (2012).&nbspMeta-heuristics:theory and applications.Springer Science &amp Business Media.

Pólya, G., Tarjan, R. E., &ampWoods, D. R. (2013).&nbspNoteson introductory combinatorics&nbsp(Vol.4). Springer Science &amp Business Media.

Shilov, G. E., &amp Silverman, R.A. (2012).&nbspAnintroduction to the theory of linear spaces.Courier Corporation.

Sylvester, J. J., &amp Baker, H.F. (2012).&nbspThecollected mathematical papers of James Joseph Sylvester&nbsp(Vol.3). Cambridge University Press.