Graph Theory

Graph theory is a branch of mathematics that looks at the relationship between objects. I know this might sound a little vague, but to get the basic picture of what graph theory is, I’d like to take a look at the following image:

The bridges of Königsberg. Image: Bogdan Giuşcă, via Wikimedia Commons.

The bridges of Königsberg. Image: Bogdan Giuşcă, via Wikimedia Commons.

The image above is a drawing of the Königsberg bridges, located in Königsberg, Germany in 1736. This problem was the beginning of graph theory and no one even knew it. It can be defined by the following:

The Königsberg bridge problem asks if the seven bridges of the city of Königsberg, formerly in Germany but now known as Kaliningrad and part of Russia, over the river Preger can all be traversed in a single trip without doubling back, with the additional requirement that the trip ends in the same place it began.

Proof by Euler

Leonard Euler, in the year 1735, introduced a counter proof to the problem described above. He realized that the only important issues in the problem were the bridge crossing sequences. Using this abstract he created two new terms, “vertex” or “node”, and “edge.” In the above picture each unique landmass would be classified as a vertex, while each bridge is classified as an edge. Euler’s resulting image would look something like the following:

The graph that represents the bridges of Königsberg. Image: Riojajar, via Wikimedia Commons.

The graph that represents the bridges of Königsberg. Image: Riojajar, via Wikimedia Commons.

The image above is described as a graph. Within a graph, it does not matter the exact location of each node. However, the connection(s) formed between nodes does matter. Edges between nodes can either be curved or straight, because it’s not important to the graph structure, they are simply showing how each object is connected.

Euler then describes the process of his counter proof by first describing what is now known as the “degree” of a node. A degree of a node is described as how many edges it has (one, two, etc.). His proof says that within a connected graph (there can’t be any nodes that are alone, i.e. not connected to any other node) there can be either zero, or two, nodes that have an odd degree. This proof was monumental in his time and was later validated by Carl Hierholzer.

Traveling Salesman Problem

One of most studied graph theory problems in the field of Computer Science is the Traveling Salesman Problem or TSP for short. The basic problem definition states that given a list of cities and the distances between them, find the shortest path between all cities, where each city is visited exactly once and the “salesman” must return to the original city. Currently there are no algorithms that can solve this problem in polynomial time (polynomial time is described as O(na), where n is the number of cities and a is a constant integer). Active research in solving this problem and many algorithms come from general heuristic solutions, which are currently the fastest ways to solve the TSP. The TSP is used in many different fields including logistics, transportation and even microchip production.

Unsolved Problem

There is one major unsolved problem in graph theory known as the “Longest path problem.” The problem is described as finding the longest path in a graph, without repeating vertices, by counting the number of edges the path contains. This problem is classified as NP-hard, implying that it cannot be solved in polynomial time or solved at all (this definition of NP is also one of the Millennium Prize Problems, asking if P = NP, check out http://en.wikipedia.org/wiki/P_versus_NP_problem for a quick definition).

Conclusion

Graph theory is a very interesting subject and it has a lot to offer. Many mathematical and computer science problems have been solved using graph theory. I believe that with continued research, it will be known if the “Longest path problem” can be solved. There are many companies such as FedEx and UPS that are very interested in the traveling salesman problem, because it could greatly reduce the amount of fuel used delivering packages, thus reducing global emissions and saving natural resources. I find graph theory to be a very interesting subject and I hope in due time humanity will have all of the answers to graph theory’s most problematic questions.

References

http://plus.maths.org/content/maths-minute-bridges-konigsberg

http://www.math.uwaterloo.ca/tsp/apps/

http://en.wikipedia.org/wiki/Graph_theory

http://mathworld.wolfram.com/LongestPathProblem.html

http://world.mathigon.org/Graph_Theory

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s