Why It Matters: Graph Theory

Why understand graph theory?

Silhouette of a businessman running with briefcase in hand against a dark backgroundYou shined your shoes and packed your briefcase.  Now it’s time to stop in at each of your clients now that you are the main sales representative for your company.  You have nine clients in the same region, and you have mapped them out by determining the time it will take you to get from one to the other in minutes.  You labeled the clients A through I, and your original plan was to visit them in alphabetical order.  Sounds easy enough.  The problem is that when you finish up with client G, you realize you left a very important sample back at Client C.  How can you determine the shortest path back?  And then once you get it, how can you decide the fastest route to your next client?

 

You can start by making a diagram showing the travel time between each client.  However, there are multiple paths that are possible from any one client to another. Your diagram looks a bit overwhelming – it isn’t immediately obvious which route would be the fastest.

Graph diagram connects locations A through E. A connects to B by 8 units, B to C by 8 units, C to D by 10 units, D to E by 8 units, E to F by 7 units, F to G by 5 units, G to H by 5 units, and H to I by 5 units. In addition, B connects to D by 14 units, B to F by 20 units, F to I by 15 units, and G to I by 12 units.

 

Fortunately, you’ll learn how to solve the problem as you complete this module.  You will figure out how to interpret diagrams such as this and use them to make logical decisions, such as which way to go to keep your clients happy and close the deal.