Geogebra Applet For Graph Theory



Due Tuesday Nov. 30, 2015


Background

The Voronoi assignment model is used every day by geographers, climatologists, and even networkers. I shows a practical application for graph theory that mixes with geometry. This model subdivides a plane into different sections using straight lines. This applet focuses on Three-Site Voronoi Diagrams applied to delivering trucks. With the age of computers an order can be made anywhere in the world and then the company has to figure out the cheapest and fastest way to deliver their package. If there is three airports in the area and the company wants to figure out which airport if the closest a Three-Sit Voronoi Diagram could help in that situation. It divides the map into regions that are closest to the airport. To construct these regions a graph is created with vertices at each airport, and edges connect them forming a triangle. Then each of the perpendicular bisectors are found which have a common point called the circumcenter. This divides the map into six sections with six rays. Now the trick is to pick the three rays, one from each perpendicular bisector, that each separate one vertex from the other two. Now follow the app and the questions below to visualize this process.


Questions

  1. Notice the three points of interest. Now click show triangle and show perpendicular bisectors. Pick and name below three rays that divide two vertices from the other one.




  2. Click show the Voronoi Assignment Model and refine your answer from question1. As you move around the points, do the three rays chosen always correctly divide the map into three sections, each one containing one of the points of interest? How would you solve this problem?




  3. Click show the map of Cache County High Schools. This shows three high schools and their positions. Follow the directions on the applet as to where to place the vertices to answer the following questions.
    1. If you live in Newton which school should you attend according to the model?




    2. If you live in Honeyville which school should you attend according to this model?




    3. Why do not school districts follow Voronoi models exactly when deciding how to assign students to a school?




  4. Click show map of USA major airports. If the only three airports in the USA where Chicago, San Antonio, and Phoenix, which would you go to if you lived in eastern Colorado?




  5. Uncheck all but show map of the USA major airports and Complete Graph. This shows air routes connecting each one of the ten airports to all the others. Name two advantages and disadvantages of using a complete graph or point to point system to connect all the airports.




  6. Check only show map of USA major airports and Central Locations #1. Name two advantages and disadvantages of using a central location for a hub and spoke graph.




  7. Look at Central Location #1 and #2 and make a conjecture about which one would conserve more on miles.




Download the Worksheet to Print

Questions for Applet