Graphing the Spread of Disease
Graph theory is used to show the spread of disease. Node 4 is the primary carrier who transmitted to nodes 2, 5 and 6, which further spread the disease to nodes 1, 3 and 7.Copyright Centers for Disease Control and Prevention (left), and 2006 User:ZeroOne, Wikimedia Commons {PD} (right) http://hivtest.cdc.gov/reasons/images/slides_4.jpg http://commons.wikimedia.org/wiki/File:Graph_theory_tree.svg
Students simulate disease transmission by collecting data based on their proximity to other students. One option for measuring proximity is by having Bluetooth devices "discover" each other. After data is collected, students apply graph theory to analyze it, and summarize their data and findings in lab report format. Students learn real-world engineering applications of graph theory and see how numerous instances of real-world relationships can be more thoroughly understood by applying graph theory. Also, by applying graph theory the students are able to come up with possible solutions to limit the spread of disease. The activity is intended to be part of a computer science curriculum and knowledge of the Java programming language is required. To complete the activity, a computer with Java installed and appropriate editing software is needed.
Graph theory is the study of graphs in computer science and mathematics. A graph is a mathematical structure used to model relationships between the objects in a set of objects. In this context, graphs have vertices or "nodes" and a group of edges, which connect pairs of vertices. In computer science, software engineers use graphs to represent communication networks, data organization, computational devices and the flow of computation. One example of graph theory used by computer and software engineers is cell phone networks. Your phone is a node along with repeater towers and base stations. When you make a call, you connect with other nodes and those connections become edges in the graph. Another example is social networks that software engineers exploit on sites like Facebook to market products. By using graph theory, software engineers use the connections (edges) to your friends to find people who might also want to buy products of interest to you.
After this activity, students should be able to:
- Use graph theory to complete depth first search (DFS) and breadth first search (BFS).
- Analyze of the spread of disease using Graph theory concepts.