Occupy Math has some doubts that teaching people calculus is the correct choice for the more-or-less default advanced math class in college or university. My TEDX talk Why teach calculus? makes the case against calculus in this frontier role. Today I’d like to talk about one of the alternatives – graph theory. These aren’t the pictures of functions that are called “graphs” in algebra or trig class. These graphs are dots, connected by lines.
Graph theory is so simple that sixth graders can learn it – and it also introduces the real discipline of mathematics, logical thinking.
Here is a problem that is often used to introduce graph theory. Suppose there are several people at a party. Any pair of people are either friends or strangers. Is it possible for each person to have a different number of friends? A graph gives us a simple way to make a picture from this. People are dots and the lines between them denote friendship links:
This graph doesn’t solve the problem – we labeled each person with their number of friends and there are two people with 3 friends so everyone doesn’t have a different number of friends. This problem, phrased in human terms, shows how the graph formalism strips the problem down to essentials: find a dot and line diagram with a different number of lines ending at each dot. Can you figure out what’s going on with this problem?
Graph theory is useful in urban planning.
The pictures below are diagrams of the streets of a neighborhood. On the top the outlines of the building are shown as colored polygons, on the bottom is the “one block apart” diagram (graph) of just the street corners. The problem is this: We want to place water fountains so that every corner either has a fountain or is one block from a corner that has a fountain. Since fountains cost money, we want to do it with the fewest possible fountains. This problem is a puzzle – tweet us your answer and the best answer – breaking ties by time of arrival – will get a unique fractal image from Occupy Math. This problem is an example of the dominating set problem.
Tasks and times to make cookies
|Get ingredients||25||A||Add chips and walnuts||3||G|
|Grease cookie sheets||5||B||Spoon dough onto sheets||5||H|
|Pre-heat oven||10||C||Bake cookies||18||I|
|Mix dry ingredients||3||D||Move cookies to cool||10||J|
|Mix wet ingredients||3||E||Eat cookies!!||fast||K|
Now we make a picture where we have all the jobs and an arrow if one job has to be done just before another.
The numbers are all times – each arrow is labeled with the amount of time the task at its beginning takes. The red numbers are the number of minutes before the cookies are ready that the tasks must be started. The red numbers are computed by going backward through the graph. Notice that some tasks are done at the same time – this means you need an assistant to mix the dry ingredients. This cookie planning technique is an example of one version of the critical path method. The graph is called a directed graph because it has arrows instead of just lines.
The examples in this post are just a tiny sample of what’s available in graph theory. The water-fountain example extends to placing new gas stations or finding where to put fire stations to minimize response time. The famous map coloring problem is a graph theory problem. Graphs can be used in conflict resolution by representing conflicts as edges – this lets you schedule meetings where no-one is supposed to be in two places at the same time.
Graph theory contains everything from pure math to the very applied problems shown in this post.
Learning graph theory would serve potential citizens – who are not going to be scientists or engineers – much better than the math we teach them now. Even the scientists and engineers would benefit if they were taught graph theory in addition to calculus. Got an opinion on this? Tweet or comment!
I hope to see you here again
University of Guelph
Department of Mathematics and Statistics