Lesson Graph Theory in Drama

Learning Objectives

After this lesson, students should be able to:

• Explain the basic concepts of graph theory.
• Apply graph theory to the analysis of a network.
• Explore the practical concepts of graph theory through questioning.

Educational Standards

Each TeachEngineering lesson or activity is correlated to one or more K-12 science, technology, engineering or math (STEM) educational standards.

All 100,000+ K-12 STEM standards covered in TeachEngineering are collected, maintained and packaged by the Achievement Standards Network (ASN), a project of D2L (www.achievementstandards.org).

In the ASN, standards are hierarchically structured: first by source; e.g., by state; within source by type; e.g., science or mathematics; within type by subtype, then by grade, etc.

International Technology and Engineering Educators Association - Technology

State Standards

Worksheets and Attachments

Pre-Req Knowledge

The teacher should have knowledge of graph theory and its basic concepts. Students need knowledge of graph theory including the vocabulary: nodes and edges, which can be prior knowledge or introduced in the lesson.

Introduction/Motivation

(Introduce the vocabulary of graph theory to students prior to the questioning in the lesson. An understanding of the vocabulary terms is critical for successful lesson completion. Either provide students with definitions for these words (graph theory, node/vertex, child vertex, sibling vertex and edge) or have students look them up. Then have a discussion about these terms and their meanings so that everyone understands them.)

In this lesson, you will explore the concepts of graph theory. Many different types of engineers represent different situations using graph theory. Electrical engineers and computer engineers use graph theory to represent integrated circuits. By using graph theory components, density can be maximized to optimize processing speed and electrical efficiency. Network engineers use graph theory to represent communication networks with terminals and relay stations as the nodes. Communication links between the network devices are the edges. Any situation that has linked items can be represented using graph theory. Structural engineers use graph theory to represent the forces in a truss. The nodes represent the pinned joints in the truss. Edges represent the rods in the truss with its end vertices corresponding to the joints that connect the rod to the truss. Edges are also used to represent external forces and reactions. Can you think of any possible applications for graph theory?

Believe it or not, some engineers use graph theory to understand relationships between people. This is the case for engineers who work for companies such as Facebook, where an understanding of relationships between people is critical for advertisement and revenue. In this lesson, and its associated activities, we will focus on using graph theory to represent relationships between people. At the same time, we want to remember that many other engineering applications use graph theory. Questioning will be used to guide you to think about graph structures, purposes and layouts. As you answer the following questions, you will write and draw graphics.

• How do people define who is in a relationship with another person? (Answer: Relationships are defined by communication.)
• How can we mathematically determine the quality of a relationship? (Answer: One measure would be the quantity of communication. Another would be the quality of communication. In close relationships, a large quantity of communication builds quality communication.)
• How can a relationship be represented in a graph? (Answer: Two nodes could represent two people, and their relationship can be shown as an edge.)
• How can a relationship be tracked in a piece of literature? (Answer: The quantity of communication between characters.)
• In a piece of literature, what character has the greatest social impact? (Answer: A character who communicates with a large numbers of other characters. A character who does something significant, which affects other characters.)
• What variables on a graph can we change to represent importance of a character? (Answer: Size of nodes. Color of nodes. Note: Typically, nodes of equal importance are represented using the same size and color of node. Edges are not color-coded or changed in size because it would make the graphs very difficult to look at and analyze.)
• What are some real-world social relationships that can be tracked in this way? (Answer: Social groups, advertising research, social networks such as Facebook, MySpace and Twitter.)
• What is the practical side of discovering who has the greatest social impact in real life? (Answer: Advertising, identifying trend setters vs. followers, understanding people [human science].)

(As the questioning progresses, expect students to begin to see real-world implications of graph theory and how it could be used to represent existing relationships). Then, students can use the associated activities, Graphing Your Social Network and Using Graph Theory to Analyze Drama, to practice applying this technique to real world examples.

Lesson Background and Concepts for Teachers

Graph theory is the mathematical study of graphs. A graph consists of a set or collection of vertices or nodes and a set or collection of edges that connect the vertices. As an illustration, a graph defined by vertex set V= {1, 2, 3, 4} and edge set E= {(1, 3), (1, 4), (2, 3), (2, 4)} has the diagram shown in Figure 1. Vertices that are connected by an edge are said to be adjacent. The degree of a vertex is the number of edges connecting to the vertex as an end point. In the Figure 1 example graph, all vertices have a degree of 2. Some of the different types of graphs are the complete graph and the regular graph. A complete graph is a graph in which every vertex is adjacent to every other vertex. A regular graph has the same degree on all vertices.

An adjacency matrix for a graph with n vertices is an n x n matrix where entry (i, j) is 1 if there is an edge in the graph between vertex i and j, otherwise the entry is 0. The adjacency matrix shown in Figure 2 is for the graph shown in Figure 1.

An adjacency list for a graph has a row for each vertex and contains the vertex label followed by the vertex labels of adjacent vertices. The adjacency list for the graph in Figure 1 is shown in Figure 3.

A path in a graph from vertex v to u is a sequence of edges where the first edge starts at v, each successive edge connects to the previous edge, and the final edge terminates at u. A path from 1 to 2 in the Figure 1 graph would be: (1, 3), (3, 2). A vertex v is reachable from vertex u, if there is a path from v to u. A graph is connected, if every vertex is reachable from every other vertex, otherwise the graph is considered disconnected.

Associated Activities

• Graphing Your Social Network - Students analyze their social networks using graph theory. They gather data on their own social relationships, either from Facebook or the interactions they have throughout the course of a day, recording it in a spreadsheet and using Cytoscape (a free, downloadable application) to generate social network graphs that visually illustrate the key persons (nodes) and connections between them (edges). The nodes (people in students' social networks) in the Cytoscape graphs are color-coded and sized according to their importance. After the analysis, the graphs are further examined to see what can be learned from the visual representation.
• Using Graph Theory to Analyze Drama - Students analyze dramatic works using graph theory. They gather data, record it in a spreadsheet and use Cytoscape (a free, downloadable application) to generate graphs that visually illustrate the key characters (nodes) and connections between them (edges). The nodes are color-coded and sized according to the importance of the node. After the analysis, the graphs are further examined to see what the visual depiction of the story tells readers about the inner workings of the dramatic work.

Vocabulary/Definitions

child vertex: Nodes in a graph that are connected to a given node.

edge: A connection between nodes.

graph theory: The study of mathematical structures that model relationships between objects from a collection.

node/vertex: The fundamental unit of which graphs are formed.

sibling vertex: Nodes in a graph that are not directly connected to a given node. Sibling vertices are both children to the same parent.

Assessment

Formative Assessment

Observations: As students are engaged in the lesson, ask the following (or similar) questions:

• Are students able to identify their connections correctly?
• Do students know what nodes of a network are?
• Do students know what edges of a network are?
• Do students understand the difference between child nodes and sibling nodes?

Summative Assessment

Writing: Assign students to complete the following writing prompts, as provided on the Graph Theory in Drama Summative Assessment, and below. Review their answers to assess their mastery of the subject matter before conducting the associated activities.

1. Explain node, child node, sibling node and edge as related to graph theory. (Example answer: A node or vertex is a point on the graph. In a social network or dramatic work represented by a graph, it is a person. An edge is a line connecting two nodes representing a connection or relationship. Child nodes are the nodes that are directly connected to a given node and sibling nodes are nodes in the graph that are not directly connected.)
2. Describe how engineers use graph theory. (Example answer: Graph theory can be used to represent relationships present in a system. Many different types of engineering use graph theory. Computer engineers use graphs to represent networks and integrated circuits. Structural engineers use graph theory to represent the dynamics present in structural members like trusses.)
3. Explain how you can apply a mathematical concept like graph theory to literature and what you can learn from that application. (Example answer: The concept of graph theory can be used to show character relationships in a visual way. From the activity on dramatic networks, characters with more connections can be represented with larger nodes and others with fewer connections by smaller nodes. This representation easily helps viewers see who is important in the story and the relationships that exist.)

Other Related Information

It is recommended to conduct the social networks activity (Graphing Your Social Network) first and then the dramatic networks activity (Using Graph Theory to Analyze Drama), but the order is not that critical. In both activities, students gain practice with graph theory vocabulary, including node, edge, betweeness centrality and degree on interaction, and learn about a range of engineering applications of graph theory.

Copyright

Contributors

Supporting Program

Acknowledgements

The contents of this digital library curriculum were developed as a part of the RET in Engineering and Computer Science Site on Infusing Mobile Platform Applied Research into Teaching (IMPART) Program at the University of Nebraska-Omaha under National Science Foundation RET grant number CNS 1201136. However, these contents do not necessarily represent the policies of the National Science Foundation, and you should not assume endorsement by the federal government.