Teacher Manual Table of Contents
Beyond Numbers table of contents
Home page

PURPOSE:

This explainer will present information to acquaint visitors with graph theory and a practical application.

OBJECTIVES:

1. The visitor will use graph theory to solve a real-world problem.
2. The visitor will find more than one solution for a building.

MATERIALS:

a hinged plex array of 4" by 4" cubes with tops and bottoms open
16 ethafoam braces:
a low surface to hold the array (or a floor)
a mat
writing surface such as a white board , or use laminated chart of the array
wipe off markers (for laminate, use water soluble markers)
signs: see attached
chart with 2 by 4 set of vertices
tinkertoys

DEFINITIONS:

array - a rectangular display of dots
brace - something that imparts rigidity to a framework
combination ­ the arrangement of a number of things into various groups, as a, b, and c into ab, ac, and bc. There are 3 combinations of a,b, and c. If order is important a,b, and c form 6 permutations.
written as , it means the number of ways r items can be selected from a collection of n items.
combinatorics - the study of combinations and permutations (selecting r items from a group of n items when order counts.
combinatorial graphs - graph (networks) that describe combinations or permutations
complex plane - the Cartesian graph of all complex numbers
congruent­ when any geometric shapes are compared, and the angles are found to be equal , the shapes are called congruent.
connected graph ­ a graph (network) in which any two of the vertices can be joined by a path; this means that it is possible to travel from any vertex to any other vertex along consecutive edges of the graph.
dimension - the number of parameters needed to specify the position of a particular point in space
edge ­ a line or border connecting vertices (points)
graph (network) - A graph is a set of points (called vertices) and a set of lines (called edges) joining these vertices; a finite set of dots and connecting links. The dots are called vertices and the links are called edges. Each edge must connect two different vertices. Two vertices are adjacent if there is an edge joining them.
graph (network) theory - the mathematics of connections; related to combinatorics
grid - in this lesson, a system of coordinates with rows and columns
mapping coordinates - marking points by assigning two or more values to them; with two points, one is for the horizontal axis and the other is for the vertical axis.
network ­ a system of lines and line crossings, another word for graph which distinguishes the graph (network)/network from Cartesian graphs.
path ­ a sequence of vertices in a graph (network), each one adjacent to the next one; a path along a network which covers all vertices and edges
row - a horizontal line in an array
¹ subgraph ­ a subset of vertices and connections belonging to the original graph (network)
² tree ­ any graph (network) which is connected and has no circuits. This means that there is one and only one path joining any two vertices
vertex (VUR­teks) ­ point connected by edges, except when there is only one vertex when there will be no edges. If two edges cross as they connect vertices, this is a crossing but not a vertex.
A vertex is called an odd vertex or an even vertex depending on the number of edges which meet there. For example, two edges ­ even, three edges ­ odd.
vertices (VUR­ti­sees) ­ plural of vertex

Keep in mind that top row vertices represent rows and the bottom vertices represent columns. The edges have to connect rows with columns; so all the edges in our graph will b diagonal or vertical lines. As you draw a graph make one connection at a time and relate it to the diagram of the array.

EXHIBIT REFERENCE:

The topics in this explainer are related to the Maryland Science Center Structures exhibit, and Beyond Numbers components:

Introduction to Graphs Electromechanical Interactive

Perfect Matching Manual interactive

Nine Fire Stations Electromechanical Interactive
 
 

PROCEDURES:
Present the plex 4" by 4" array lying flat on the mat over the diagram so that nothing interferes with it's flexibility in length or width. Tell the visitors that the array is in need of help. Show how flexible and floppy it is.

Show how braces can be used to maintain the structures rigidity. Put ethafoam braces in one frame. Allow visitors to put braces in each frame.

Tell visitors that "a builder uses tools. There are the materials of the structure, - plastic, cord, braces..., the machines to the put the structure together, the labor to put the structure together, the blueprints of the structure, ... One tool that can help a build save money on her other tools is mathematics. " Tell the visitor that you'll be "showing how graph (network) theory, a branch of mathematics, can help a builder save money."

After all the braces are in the structure pull one out .

"Hey maybe I can save some money if I use less material on these braces. How many can I pull out?
There are at least three ways to figure out how many braces I can pull out to minimize the number that have to remain. " Show signs:
Use trial and error.
Copy someone else's' work.
Use math.
Try trial and error first. Have visitors suggest and take some out. Try the device. If someone uses reasoning to decide where to pull out the braces, point out that this is not really trial and error. Discuss the advantages and disadvantages to trial and error.

Suggest they try the second method: Copy someone else's work. Suggest that this is not a bad idea, that people do it all the time. Then, ask if anyone has a diagram to use. (If someone on the staff decides to play a joke on you and actually provides one, go ahead and use it) Discuss the advantages and disadvantages to copying someone else's work.
Suggest that the visitors try the mathematics in
graph (network) theory.
"Let's represent each possible row with a dot.
and in another row, we'll represent each column with a dot. Each dot is a vertex of our graph. Every time we connect row and column vertices with line (edges) , we are indicating the location of a brace.
 

[Show a completed graph] Here is a graph.
 
 

There are 16 edges representing every column
of every row with a brace. But we know that all
these braces are not necessary. We want to use
the minimum amount of materials in order to
save money."

Tell the visitor that mathematicians have learned
that the minimum amount of bracing is the
minimum number of edges needed to connect
all the vertices of the graph. There are several
combinations of edges to do this - after all, this is
combinatorics.

"Let's get a fresh set of vertices for you to connect" Pull out a cartoon connect-the-dots picture. "Oops!" Take out the correct graph.

Have the visitor draw in the graph, making one connection at a time. Each time she draws an edge, you put an X in the corresponding place of the diagram.

for example:
is represented by
 
 
 
 
 
 

Keep asking the visitor to check if all the vertices are connected. Have her point out how they are connected. If all vertices are connected and there are more than seven edges, suggest that there is an edge that could be removed.

Use tinkertoys to show how, when there are 7 edges connecting all vertices, the graph forms a tree.

Construct the plex grid according to the diagram. Test the plex for rigidity.

If you like, you may take a Polaroid picture of the visitor, the graph and the grid to display for other visitors. Then you can challenge future visitors to find different solutions.

BIBLIOGRAPHY:

Beyond Numbers Teacher Guide, Maryland Science Center 1995 ­ lesson plans on Critical Paths, Planar Graphs and Map Coloring

Greenleaf, Yvonne and Jeanette McGillicuddy of the Mathematics/Computer Science Department at River College, Nashua, New Hampshire"Trees and Soap Bubbles: Applications in Graph Theory" a workshop given at the NCTM (National Council of Teachers of Mathematics) 73rd annual meeting, April 6­9, 1995, Boston Massachusetts

Ore, Oystein; Graphs and Their Uses, revised and updated by Robin J. Wilson, The Mathematical Association of America, 1990

COPYRIGHT: 1995 Maryland Science Center

AUTHOR:

Cathy Brady, Math Specialist
Maryland Science Center
 

^{1, 2} Greenleaf, Yvonne and Jeanette McGillicuddy