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)