Dr. VásquezLesson 1: Discrete Math – Graphs & Paths
TexasStateUniversityFall 2005
Project La Costa
Year 2 After School Program
Math Lesson 1
Discrete Math – Graphs & Paths
Dr. Selina Vásquez
Dr. VásquezLesson 1: Discrete Math – Graphs & Paths
TexasStateUniversityFall 2005
Dr. VásquezLesson 1: Discrete Math – Graphs & Paths
TexasStateUniversityFall 2005
Department of Mathematics
Texas State University-San Marcos
San Marcos, TX78666
July 12, 2005
Project LaCosta is supported by NSF Grant ESI-0423115
Texas State University-San Marcos is part of the TexasStateUniversity System
Discrete Math
Graphs & Paths
Background
Consider the following diagrams. Which of the following diagrams can be drawn without lifting your pencil from the paper or repeating any of the sides? (a, b, d, f, g, h)What are some common properties of the diagrams you chose? (allow students to brainstorm; answers may vary)
a) b) c)
d) e) f)
g) h) i)
Activity
By exploring these questions, we begin our study of a mathematical structure called graphs. The study of graphs is useful in answering problems that occur in management science, a branch of mathematics that uses mathematical methods to find optimal solutions. For example, services such as delivering mail, setting up a garbage pick-up route, collecting money from parking meters, and connecting wires in a computer all benefit from an efficient route with little redundancy.
Look at an example of a neighborhood. Suppose we want to help out the mail carrier by finding the most efficient route with little redundancy. We begin by representing the scenario with a graph.
Represents a mailbox
This looks like the following graph when we remove the mailboxes and make the corners and intersections into dots.
We use a graph, made up of dots, called vertices and line segments connecting the vertices, called edges, to represent the intersections and streets in the following way.
If we want an optimal route for delivering mail to the houses along these streets, we are looking for the path that will go down every street but avoid going down streets more than once; in other words avoid redundancy.
Exercise A:
Represent each of the neighborhoods as graphs.
1.2.
Now, let’s clarify some of the terms. A graph consists of a finite set of vertices together with edges, connecting pairs of vertices. We often label vertices with letters like A, B, C, M, X, Y, Z etc. as in Figure 1.
CX
Figure 1 A Z
B M Y
A path in a graph is a connected sequence of edges that begin and end at a vertex.
Figure 2 shows paths with directed arrows. The sequence is also written to its side.
B
Figure 2 A
A ABCAD
ABCA C
C B
D
The graphs above can have different paths as in Figure 3
Figure 3
BADCBAC
AACBA
A C
C B
D
To traverse a graph means to follow a continuous path covering every edge of the graph once and only once. You may recall that in the first activity you were asked to identify graphs with this property. At that point you used trial and error. Can you find a rule to determine which networks can be traversed? You may want to consider the importance of order, the number of edges that meet at a vertex. (A network can be traversed if and only if the number of odd vertices is zero or two.)
Exercise B:
1. Find a path in each of the following graphs. Make sure you put in your directed arrows and write down the sequence on the side of the graph.
2. Which of the following graphs can be traversed? Justify your answer by showing the path and by using your rule.
Discrete Math Exercises - Solutions
Exercise A:
Represent each of the neighborhoods as graphs.
1.2.
Exercise B:
1. Find a path in each of the following graphs. Make sure you put in your directed arrows and write down the sequence on the side of the graph.
These are just one possible path. There can be more correct answers.
ABCADBABACBDA ABCDEADBECA
2. Which of the following graphs can be traversed? Justify your answer by showing the path and by using your rule.
cannot be traversedcan be traversed
(A=3, B=3, C=3, D=3)(A=4, B=2, C=5, D=2, E=5, F=2, G=4)
can be traversedcan be traversed
(A=4, B=2, C=2, D=4, E=2)(A=4, B=2, C=4, D=2, E=2, F=2)