Graph Theory in Drama
Giáo viên:
Tổng quan
Summary
Students use graph theory to create social graphs for their own social networks and apply what learn to create a graph representing the social dynamics found in a dramatic text. Students then derive meaning based on what they know about the text from the graphs they created. Students learn graph theory vocabulary, as well as engineering applications of graph theory.
Engineering Connection
Graph theory is the study of graphs and is applicable in computer science, mathematics and engineering. A graph is a mathematical structure used to model relationships between the objects in a set of objects. Graphs in this context 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. One example of graph theory used by computer/software engineers is the multihop cooperative relay communication networks in which the network is comprised of a base station(s) and relay stations (nodes) that communicate information to mobile communication devices. Another is a social network that software engineers are exploiting on sites like Facebook to market products to consumers. Software engineers can use graph theory to represent the structure of a website. The vertices are the available web pages and the edges are the connections (directional) between pages.
In the design of integrated circuits (ICs) for electronic devices, electrical engineers and computer electronic engineers also employ graph theory. ICs have complex layered microcircuits that can be represented as nodes interconnected by lines or arcs. By using graph theory, engineers can optimize the density of components and minimize the connections to optimize processing speed and electrical efficiency.
PreReq 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.
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.
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 colorcoded or changed in size because it would make the graphs very difficult to look at and analyze.)

What are some realworld 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 realworld implications of graph theory and how it could be used to represent existing relationships.)
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.
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.
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 colorcoded 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 colorcoded 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.
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.

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.)

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.)

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.)
Contributed By
IMPART RET Program, College of Information Science & Technology, University of NebraskaOmaha
Graph Theory in Drama Summative Assessment (pdf)


00:00

Graph Theory in Drama Summative Assessment Example Answers (pdf)


00:00

Overall Activity Web Page (pdf)


00:00

Social Networks Activity Instructions (pdf)


00:00

Social Networks Assessment (pdf)


00:00

Social Networks Assessment Example Answers (pdf)


00:00

Overall Activity Web Page (pdf)


00:00

Dramatic Networks Activity Instructions (pdf)


00:00

Example Dramatic Network Graphs (pdf)


00:00

Dramatic Networks Assessment (pdf)


00:00
