Making the Connection
A graph shows a simple social network—the social connections of 11 people.Copyright State of Connecticut (top), 2011 ADuvvuru, Wikimedia Commons {PD} (bottom) http://www.ct.gov/dcf/cwp/view.asp?a=3622&Q=432386 http://commons.wikimedia.org/wiki/File:Katz_example_net.png
Graph theory is a visual way to represent relationships between objects. One of the simplest uses of graph theory is a family tree that shows how different people are related. Another application is social networks like Facebook, where a network of "friends" and their "friends" can be represented using graphs. Students learn and apply concepts and methods of graph theory to analyze data for different relationships such as friendships and physical proximity. They are asked about relationships between people and how those relationships can be illustrated. As part of the lesson, students are challenged to find the social graph of their friends. This prepares students for the associated activity during which they simulate and analyze the spread of disease using graph theory by assuming close proximity to an infected individual causes the disease to spread.
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, the flow of computation, and more. On social network websites like Facebook, software engineers exploit graph theory to market products. They analyze your "friends" and if a particular ad is relevant to you (you clicked on it), the ad shows up on the pages of your friends who have similar interests. By using content on your page and your friends' pages, content advertising is targeted to users who are most likely to buy particular products.
After this lesson, students should be able to:
- Explain the basic concepts of graph theory.
- Apply graph theory to the analysis of a network.