Significance and Applications of Graph Theory

The world today is full of questions and problems that need to be solved. This is the age of big data sets and computers that can analyze this data at speeds that fifty years ago would be viewed as impossible. Companies spend millions analyzing relationships between their customers’ preferences, just to predict what they will buy. Euler’s design of vertexes linked together can be used to represent millions of relationships. Then this graph can be used over and over again to make necessary connections. ″Enterprise efforts in fraud detection, master data management, and network and IT operations are vastly improving, thanks to relationship-based insight rooted in graph database usage″ (Elfrem, 2015). There is no end to applications of graph theory and it is employed for new uses almost daily.


List of Applications of Graph Theory:

Geogebra Applet For Graph Theory




Background

The Voronoi assignment model is used every day by geographers, climatologists, and even networkers. It shows a practical application for graph theory that mixes with geometry. This model subdivides a plane into different sections using straight lines. Also, 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 are three airports in the area and the company wants to figure out which airport is 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, determine whether 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 were 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

BACK TO THE TOP