Graph Theory is an area of mathematics that uses constructs called graphs to model many relations and processes found in real-world problems. The graphs consist of vertices (points or nodes) connected by edges (segments or arcs or loops). This area of mathematics has applications in computer science, biology, chemistry, linguistics, physics, chemistry, sociology, and more. Can I dare say that Graph Theory is ubiquitous? So, imagine my lack of surprise when I was watching a TED talk today and saw Graph Theory in action. The link below takes you to the talk “How Trees Talk to Each Other” by Suzanne Simard. The talk does not get into the mathematics, but there are some images that caught my attention. One was that of a fractal, starting at 8:36 in the video. (This grabbed me, as my Master’s thesis talked about using fractals to monitor the health of forests. Sadly, the image had nothing to do with her mathematics.) The next was a graph, which appears at 10:40 in the video. She does talk about how that graph is used to model connections in a forest, giving me a bit of mathematical excitement. Despite the lack of a whole lot of mathematics, this video is well worth a watch. Check it out, and watch out for the bit of Graph Theory.
The people of Konigsberg, Prussia were prone to taking walks after dinner. Their town had the Pregel River running through, dividing the town into 4 land masses: one on each side of the river and two islands in the river. The land masses were connected by 7 different foot bridges. The people wondered, could they walk around and cross each bridge exactly one time each?
When Leonhard Euler came into the picture, they no longer had to ask. They knew! You see, Euler turned it into a graph theory problem. The land masses were represented with points called vertices, and the bridges were represented with segments or curves called edges. It turns out that every land mass had an odd number of bridges coming out of it. So, the graph had more than two odd vertices. This tells us that it is impossible to take the walk that the Prussians wanted to take. Always, a bridge would have to be used more than once in order to cross every bridge.
We can thank Euler for not only solving this problem but developing the field of graph theory, which has many uses today. Some instances where graph theory comes in handy? Graphs can be used to map out family trees, train tracks, highways, data networks, and much more. Local to me, an application has been the planning of walking paths at Bok Tower Gardens in Lake Wales, Florida. The garden planners created a graph of the various points of interest and the paths that may be used. They are striving to make this picturesque place more accessible to those with handicaps, and graph theory is a vital tool in that process.