Trick-or-treating was my favorite part of Halloween growing up. I loved to walk around, see other people’s costumes, and collect a hearty stock of candy to eat over the next few months. Eventually, I figured out the houses that gave out either the most candy or my favorite candy and made sure to stop at those on my trick-or-treat route.
If I really wanted to, I could have taken this route of planning to the next level by using a branch of mathematics known as graph theory. It has a confusing name since the term “graph” invokes memories of x-y plots of functions for many of us. Mathematicians aren’t the most creative in naming things, however, and stole the term to have a new meaning in the context of graph theory.
Here, a graph is simply a collection of two objects, called vertices and edges. Vertices are points, and edges connect two points together. So what might be a better name for a graph is a network, consisting of a series of connections (edges) that meet at junctions (vertices).
In the case of trick-or-treating, we want the vertices to represent houses, and the edges to represent paths from one house to another. Furthermore, it would be good to know how far away houses are from each other, or how desirable the candy at each house is. To quantify this, I can assign weights to the edges, perhaps having higher weights correspond to a shorter distance or a good next stop for candy.
Graph theory seeks to provide tools for gaining information from graphs, which in general can be quite complex. For trick-or-treating, after constructing the graph and doing calculations with the weights, my goal would be to have a path including houses (the vertices) and paths between them (the edges) that takes the shortest amount of time and gets the best candy. I would’ve loved to have this information as a kid!
In a similar vein to the trick-or-treating example, graphs are used in route planning algorithms on Google and Apple maps to minimize travel time or find routes with other desirable qualities like no tolls. They can also be used to analyze traffic patterns, which help urban planners minimize congestion.
Many other algorithms in computer science rely on graph theory. Search engines use graphs to determine the top websites to suggest based on the keywords typed in the search bar. Social media networks employ similar algorithms to model interactions among accounts and organize your feed based on who you follow closest. Finally, graph theory can be applied to cybersecurity to identify and shore up the weakest parts of a network.
Biology is another field that often utilizes graph theory. One common application is connectomics, the study of the nervous system. Here, it is pretty natural to understand the graph, with the vertices being the neurons and the edges being the synapses. A less clear application of graphs is in protein and gene expression. However, proteins and genes can be modeled as points (vertices) in a pathway, especially when studying metabolic or regulatory processes (with a series of edges representing the steps in these processes).
One final application I’d like to speak on is linguistics (pun intended). Here, words make up the vertices, and the edges represent similarities between words, based on parts of speech, definitions, or origin. There’s lots of active research in applying graph theory to see how languages evolve over time, as edges can also model how frequently words are used.
What I like about graph theory is that the possibilities for application are pretty much endless, as are the varieties of candy available on Halloween. Graph theory allows you to pick your favorite candy literally by giving an optimal trick-or-treating path, and figuratively through its flexibility in solving a problem in your specific field of interest.
Be First to Comment