Why It Matters: Graph Theory
You 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.
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.
Learning Objectives
Elements of Graph Theory- Define and use the elements of a graph to optimize paths through the graph
- Identify the number of vertices and edges on a graph
- Determine whether a graph is connected
- Define the degree of a vertex of a graph
- Determine the difference between a path and a circuit
- Use Dijkstra’s algorithm to find the shortest path between two vertices
- Given a table of driving times between cities, find the shortest path between two cities
- Define an Euler path, and an Euler circuit
- Use Fleury’s algorithm to determine whether a graph has an Euler circuit
