NM - Using Network Models to Make Decisions Overview

Using Network Models to Make Decisions

Image of Leonhard EulerHave you ever wondered how the mailman knows what's the best path to take to get the job done the fastest? Or how you are connected to Oprah Winfrey by less than 6 degrees of separation. In this unit, you will explore these questions and many more using special diagrams, called graphs. Graph theory was launched by the Swiss mathematician Leonhard Euler (1707-1783). Euler analyzed a puzzle involving a city with seven bridges. Would it be possible to walk through the city and cross each of its bridges exactly once? Although graph theory developed from this puzzle, you will see how graphs are used to help businesses and people make informed decisions to solve realistic problems.

Essential Questions

  • How do we go about planning a path of travel?
  • What is the best route for us to take if we want to travel the world?
  • What are the advantages of having an algorithm to find minimal spanning trees?
  • Why are different colors used in a map?
  • As a project manager, how do you decide how long a project will take and who should work on what?

Key Terms

The following key terms will help you understand the content in this module.

  • Circuit - a path that starts and ends at the same vertex
  • Complete graph - a graph in which every pair of vertices is joined by an edge
  • Critical path - the longest path in an order-requirement digraph. The length of this path gives the earliest completion time for all the tasks making up the job consisting of the tasks in the digraph
  • Edge - a line connecting two vertices.
  • Efficient network or Tree - a graph with just enough edges so that there is some path between any two pairs of vertices, but such that no edge could be removed and keep all vertices connected
  • Euler circuit - an Euler path that begins and ends at the same vertex and goes through each edge once
  • Graph - collections of vertices (points) and edges (line segments, sometimes directed)
  • Hamiltonian circuit - a path that starts and stops at the same vertex and goes through each vertex once
  • Path - a connected sequence of edges in a graph
  • Spanning Tree - a subgraph of a connected graph that is a tree and includes all vertices of the original graph
  • Vertex - a point in a graph where one or more edges end.

[CC BY-NC-SA 4.0] UNLESS OTHERWISE NOTED | IMAGES: LICENSED AND USED ACCORDING TO TERMS OF SUBSCRIPTION - INTENDED ONLY FOR USE WITHIN LESSON.