crystal clear mathematics logo

Sign up to my Newsletter

EASIER THAN YOU THINK...

Graph Theory

A graph representing the bridges and islands in KoenigsbergIt was out of graph theory that topology sprang.  Both deal with matters of connectedness and relationships.

Graph theory is the study of graphs.  But the graphs that we speak of here are different from the ones drawn on grid paper.  A graph is a mathematical structure that is used to model (pairwise) relationships between objects.  In that sense it is an abstract thing and we draw pictures of graphs (for example, the one at left).  Graphs are composed of vertices (or nodes/points) and the edges (or arcs/lines) that connect them. Graphs may be connected (when it is possible to find a pathway from any vertex to any other vertex) or disconnected.  They may be directed (the direction from one vertex to another along an edge matters) or undirected (one can travel along edges in either direction).  And there are other distinctions.  Sometimes graphs may be coloured and may be analysed on a variety of surfaces (such as the torus which is sometimes erroneously called a donut/doughnut).

As with a number of major mathematical disciplines, its story begins with that great Swiss mathematician, Leonhard Euler.  He analysed a problem that had been posed in his day, but not rigorously solved.  It is a famous problem called the Seven Bridges of Königsberg.

A drawing of the islands and bridges in KoenigsbergThe city of Königsberg in Prussia (now Kaliningrad, Russia) was, and still is, set on both sides of the Pregel River. The Pregel River contains two large islands which, in those days, were connected to each other and the mainland by seven bridges (see the map of the old city at right). The problem was to devise a walk through the city that would cross each bridge once, and once only.  All seven bridges had to be fully crossed.  Once a bridge crossing was begun, the traveller had to complete it to the other end … and no swimming or alternative trips were allowed.  The traveller did not have to start and finish at the same location.  No one had succeeded in finding a winning path, but no one had rigorously proven that it was impossible, either!  That was Euler’s challenge.

 

History and Applications of Graph Theory

A Brief History of Graph Theory

Euler's paper on the Seven Bridges of Königsberg was published in 1736.  It is regarded as the first paper in the history of graph theory.

It was not until James Joseph Sylvester wrote a paper in 1878 that the term graph began to be associated with these structures.  The first text book on graph theory, Theorie der endlichen und unendlichen Graphen (English edition here), was written by the Hungarian Dénes Kőnig (who at one time taught Paul Erdős) and published in 1936.  The publication of this book effectively marked the beginning of Graph Theory as its own branch of mathematics.  A later book, Graph Theory by Frank Harary, published in 1969, was reported by Martin Gardner to be "the definitive textbook on the subject" the world over.  It enabled mathematicians, chemists, electrical engineers and social scientists to talk to each other.

The Wikipedia article about Graph Theory mentions some significant developments in the history of Graph Theory:

In 1857, the British mathematician, Arthur Cayley, studied a particular class of graphs called trees.  His study had many implications in theoretical chemistry and marked the beginning of enumerative graph theory (which required the enumeration of graphs having particular properties).  Cayley linked his results on trees with contemporary studies of chemical composition, and some of the standard terminology of graph theory dates from this fusion of ideas (between mathematics and chemistry).

In 1852, Francis Guthrie posed an interesting problem:  When colouring any map in a plane (not on a globe), is it possible to colour all the regions with just four colours (so that no adjoining regions share the same colour)?  This became famously known as the four color problem.  Attempts to prove this true led to the development of other branches of number thoery (factorisation problems and extremal graph theory).  The four color problem remained unsolved for more than a century. The proof finally came about using computers and really took place in stages, in that the earlier proofs were not fully accepted.  You may read more in the Wikipedia articles about graph theory and the four color problem.

Some Applications of Graph Theory (Wikipedia Summary)

Many practical problems can be represented by graphs.

In computer science, graphs are used to represent networks of communication, data organization, computational devices, the flow of computation, etc. For instance, the link structure of a website can be represented by a directed graph, in which the vertices represent web pages and directed edges represent links from one page to another. A similar approach can be taken to problems in travel, biology, computer chip design, and many other fields. The development of algorithms to handle graphs is therefore of major interest in computer science.

Since syntax and compositional semantics follow tree-based structures,the field of linguistics has been greatly influenced by graph theory.  Modeling word meaning is easier when a given word is understood in terms of related words, so semantic networks are therefore important in computational linguistics. Much work has been done in understanding language as a graph.  Phonology (which uses lattice graphs in optimality theory) and morphology (which uses finite-state transducers to analyse finite-state morphology) also benefit from this field of mathematics.  Interestingly, organizations such as TextGraphs, as well as various 'Net' projects, such as WordNet, VerbNet, and others have sprung up due to the usefulness of graph theory to linguistics.

Graph theory is also used to study molecules in chemistry and physics. In condensed matter physics, the three-dimensional structure of complicated simulated atomic structures can be studied quantitatively by gathering statistics on graph-theoretic properties related to the topology of the atoms. In chemistry a graph makes a natural model for a molecule, where vertices represent atoms and edges bonds. This approach is especially used in computer processing of molecular structures, ranging from chemical editors to database searching. In statistical physics, graphs can represent local connections between interacting parts of a system, as well as the dynamics of a physical process on such systems. Graphs are also used to represent the micro-scale channels of porous media, in which the vertices represent the pores and the edges represent the smaller channels connecting the pores.

Graph theory is also widely used in sociology as a way, for example, to measure actors' prestige or to explore the spreading of rumours, notably through the use of social network analysis software. Acquaintanceship and friendship graphs describe whether people know each other. Influence graphs model whether certain people can influence the behavior of others. Finally, collaboration graphs model whether two people work together in a particular way, such as acting in a movie together.

Graph theory is also useful in biology and conservation efforts where a vertex can represent regions where certain species exist and the edges represent migration paths, or movement between the regions. This information is important when looking at breeding patterns or tracking the spread of disease, parasites or how changes to the movement can affect other species.

In mathematics, graphs are useful in geometry and certain parts of topology such as knot theory. Algebraic graph theory has close links with group theory.

A graph structure can be extended by assigning a weight to each edge of the graph. Graphs with weights, or weighted graphs, are used to represent structures in which pairwise connections have some numerical values. For example, if a graph represents a road network, the weights could represent the length of each road or the volume of traffic on it.

It took me a long time to find the right tutor who actually helped and more importantly cared about me and my marks. I would recommend Graeme enough. My maths marks improved dramatically with his help and I couldn’t have done it without him.
Ellie H (student, 2011)

See all Testimonials

Sign up to my Newsletter

Copyright © Crystal Clear Mathematics | All Rights Reserved

Website Design: www.webdesignnsw.com.au | Photography: Katieriversphotography.com.au