Section 5.1: Euler Circuit Problems

Section 5.1: Euler Circuit Problems

MANAGEMENT SCIENCE PROBLEMS: find ______ways to organize and carry out a large number of complex tasks that do not often appear possible to make ______decisions

What is a routing problem? Finding ways to ______the delivery of goods/ services to an assortment of destinations

·  Basic Questions:

o  Existence: Is an actual route even possible?

o  Optimization: If there are multiple possible routes, which is optimal route

·  Exhaustive Requirement: route must go everywhere (all destinations and all paths)

Section 5.2: Graphs

A GRAPH is a picture consisting of dots and lines (curves). This type of graph represents an area of mathematics called graph theory and is different than graphing of functions on the coordinate plane.

Formal Definition of a Graph: a structure that defines pairwise relationships (edges) with a set of objects (vertices). X related to Y if and only if XY is an edge.

Key Terms of a Graph:

VERTICES: dots or points of the graph

EDGES: lines or curves that connect any two vertices

LOOP:

MULTIPLE EDGES:

ISOLATED VERTEX:

VERTEX SET: V = {labeled vertices} EDGE SET: E = {edges labeled by 2 vertices}

Practice Problems: Identify each of the following, if they exist, in the graphs

Graph #1: Graph #2:

Vertex set: Vertex Set:

Edge Set: Edge Set:

Loops: Loop:

Multiple Edge: Multiple Edge:

Isolated Vertex: Isolated Vertex:

Graph #3:

Vertex set:

Edge Set:

Loops:

Multiple Edge:

Isolated Vertex:

Graph #4:

Vertex set:

Edge Set:

Loops:

Multiple Edge:

Isolated Vertex:

5.2 Drawing Examples: Draw the graphs described

1) V = {A, B, C, D, E} and

E = {AB, BC, CD, DE}

2) V = {A, B, C, D, E} and

E = {AB, AD, BC, CE, CD, DA, DE}

3) Vertex Set: {R, S, T, U}

Edge Set: {RS, RT, RU, TU, TS}

4) Vertex Set: {A, B, C, D, E}

Edge Set: {AA, AB, BC, BD, CD, CE, DC, DB, EA}

5) 5 vertices and 10 edges

6) 4 vertices, one multiple edge, and 6 total edges.

7) 5 vertices, 1 isolated vertex, 2 loops, and 6 total edges.

5.2 SAME GRAPHS (Isomorphic):

·  Graphs may look DIFFERENT but still represent the SAME relationships

o  You would be able to Stretch or Move parts of a graph to look like another.

·  BOTH graphs can be labeled to have the ______ VERTEX and EDGE SET

1) 2)

Which of the following pairs of graphs are the SAME?

·  Try to label the second graph similar to the first.

·  Check if you can make the same edge set as the original

Section 5.3: Graph Concepts and Terminology

ADJACENT Vertices are two SPECIFIC vertices that are joined by an edge.

·  Loop is adjacent to itself

·  If an edge exists between two vertices, then they are adjacent.

Exp #1: Is A adjacent to B?

Exp #3: Is D adjacent to A?

Exp #2: Is E adjacent to itself?

Exp #4: Is C adjacent to itself?

ADJACENT Edges are two edges that intersect (share) at a vertex.

Exp #5: Is AB adjacent to BC?

Exp #6: Is CE adjacent to BD?

The DEGREE of a vertex is the number of edges at that vertex.

·  deg(A) = degree of vertex A

·  A ______counts twice toward the degree.

·  An ODD vertex is a vertex of odd degree.

“ODD refers to edges at vertex”

·  An EVEN vertex is a vertex of even degree.

“EVEN refers to edges at vertex”

Exp #7: Find the degree of each vertex. (Label on Figure 1)

PATH is a sequence of adjacent vertices from a starting point to an ending point

·  E edge can be traveled only ONCE.

·  The LENGTH of a path is the number of edges in that path.

Exp #8: Find a path from A to E.

CIRCUIT is a path that starts and ends at the ______vertex.

Exp #9: Find a circuit for C.

Exp #10: Find a circuit for E.

PRACTICE: Figure #2

1)  Find a path from B to K passing through W but not S.

2)  Find a path from H to J of length 4.

3)  Find a circuit of length 5.

4)  Find a circuit of length 1.

5)  Find degree of each vertex (Label on Graph)

A graph is CONNECTED if any two vertices can be joined by a path.

It is always possible to travel from one vertex to any other vertex in the graph.

·  If this is not possible then the graph is DISCONNECTED.

·  A disconnected graph is made up of small connected portions or parts called COMPONENTS.

GRAPH #1: CONNECTED

{A, B, C, D, E}

GRAPH#2: DISCONNECTED

{P, Q, R, S, T, U, V, W, X, Y}

A BRIDGE is an edge in a connected graph whose removal makes it disconnected.

·  ONLY PATH between the two vertices is one edge = BRIDGE .

·  No alternative routes exist to travel between two vertices besides that edge

Bridge Example: On the front side of this sheet

·  In Figure #1: Edge AB is the Bridge

·  In Figure #2: Edge HB is the Bridge

Bridge Practice: Identify the bridge(s) in the bottom left graphs

Graph #1: Graph #2:

Draw a graph that satisfies the given properties:

#1: Has 6 vertices and 6 edges #2: Has 6 vertices and 2 bridges

#3: Vertex Set: {A, B, C, D} #4: Vertex Set: P, Q, R, S, T

Edge Set: AB, AC, AD, BD. Edge Set: PQ, QR, RR, RS, ST, TP,

#5: 3 even vertices and 4 odd vertices. #6: Graph of 5 vertices and 8 edges

6a. Connected 6b. Disconnected

HOMEWORK: p. 185 – 186 #1, 4, 5, 7, 9, 11, 13 and p. 191 #57

Section 5.4: Graph Models

Unicursal Tracing: Starting at the given dot, determine if you can trace all lines without lifting your pencil or retracing and (A) end back at the dot CLOSED, (B) end somewhere different OPEN, or (C) NEITHER. (Hint: It may be more helpful to number rather than trace edges)

FURTHER CLASSIFICATION OF UNICRUSAL TRACINGS WITH GRAPH TERMINOLOGY:

1)  How does the terms Path and Circuit apply to the unicursal tracing terms of open or closed?

2)  What additional characteristic or requirement does a unicursal tracing?

EULER PATH: A path that travels through every edge of the graph (once and only once).

EULER CIRCUIT: A circuit that travels through every edge of a graph once.

EULER =

INTRODUCTION OF GRAPH THEORY: The city of Konigsberg in Prussia (Now Russia) was set on both sides of the Pregel River, and included two large islands which were connected to each other and the mainland by seven bridges. The people of Konigsberg wanted to know if it was possible to take a stroll through the city and cross each of the seven bridges once and only once. Try on your own to find out?

What were the people trying to find an Euler Path or Circuit?

MODELING: using a mathematical concept to describe and solve a real-life problem

·  WORD PROBLEMS:

·  GRAPH MODELS:

VERTICES:

EDGES:

5.4 GRAPH MODEL EXAMPLES:

1)  FRIENDSHIPS: Moose has knows Meg, Ginger, and Betty. Jughead has knows Ginger and Betty. Archie has only ever knows Veronica. Reggie has only knows Betty.

EDGES = ______VERTICES = ______

2)  GAMES PLAYED: A typical week has the following games being played.
Monday: PIT at DC, NY at PHI, CHI at STL
Tuesday: PIT at DC
Wednesday: NY at STL, PHI at CHI
Thursday: PIT at STL, NY at DC, PHI at CHI
Friday: PHI at DC, CHI at PIT, STL at NY

EDGES = ______VERTICES = ______

Example #3 and 4: Maps of a neighborhood.

EDGES = ______VERTICES = ______

3)  Neighborhood Watch wants to be able to patrol each block the community after a rash of burglaries.

4)  The mailman needs to be figure out a delivery route for the same neighborhood.

Example #5: In a map, represent the different zones for high schools and which zones border each other for the 2009 – 2010 WSFCS School Year. .

EDGES: ______VERTICES: ______

HOMEWORK: pp. 187#15, 17, 19, 20
Section 5.5: Euler’s Theorem

INVESTIGATION

For each graph do the following:

(1)  Does the graph have an Euler Circuit or Path? (At any starting vertex)

(2)  What is the degree of each vertex of the graph?

(3)  What is the total number of edges of the graph?

Graph #1 / Graph #2 / Graph #3 / Graph #4 / Graph #5
#1 / Circuit or Path? / Circuit or Path? / Circuit or Path? / Circuit or Path? / Circuit or Path?
#2 / A =
B =
C =
D = / A =
B =
C =
D = / A =
B =
C =
D = / A =
B =
C =
D = / A = E =
B = F =
C =
D =
#3

OBSERVATION #1: What do you notice about graphs of Euler Circuits v. Euler Paths?

EULER CIRCUIT / EULER PATH
What type of vertex can you start and end at?
What do all vertices have in common? / What type of vertex can you start and end at?
What is true about the vertices in all Euler path cases?

EXISTENCE THEOREMS FOR EULER

#1: Euler’s Circuit Theorem
(a) If a graph has ______, then it ______ have an Euler Circuit.

(b) If a graph is CONNECTED and ______vertex is ______, then it has at least one Euler Circuit.

#2: Euler’s Path Theorem
(a) If a graph has ______, then it ______have an Euler Path.

(b) If a connected graph has ______ then it has at least one Euler Path STARTING at one ODD vertex and ending at the OTHER ODD one.

For each graph #6 - #8:

(1)  What is the degree of each vertex of the graph?

(2)  What is the total number of edges of the graph?

Graph #6 / Graph #7 / Graph #8
#1 / A = B = C = D =
E = F = G = / A = B = C =
D = E = F = / A = B =
C = D =
#2 / Total Edges: / Total Edges: / Total Edges:

OBSERVATION #2 - Describe a relationship between total number of edges and degree of all vertices in graph.

Is this relationship also true in graphs #1 – 5?

EULER’S SUM OF THE DEGREES THEOREM

(a) The ______of the degrees of all the vertices of a graph equals ______the number of edges.

(b) A graph ______has an ______number of ______vertices.

SUMMARY OF THEOREMS: Based on odd vertices in a CONNECTED graph.

Number of Odd Vertices

/

Euler Circuit or Path Exist?

0 odd vertices

/

2 odd vertices

/

4, 6, 8, …

(even number of odd vertices)

/

1, 3, 5, …

(odd number of odd vertices)

/

HOMEWORK: p. 188 #21 – 25 and p. 191 #53, 55 Section 5.6: Fleury’s Algorithm

Does an Euler Circuit or Euler Path Exist in each graph. If so, find by identifying the start/ end and number the edges in order.

What do Euler’s Theorems tell us about a graph?

Euler’s Theorems DO ______an Euler circuit or an Euler path.

Euler’s Theorems DO NOT______Euler circuit or Euler path.

Fleury’s Algorithm:

The Idea: “Don’t burn your bridges behind you.”

·  Fact #1: An edge can only be traveled ONCE in a path or circuit, so as you trace edges of a graph you are limiting the parts of the graph left to travel on.

·  Fact #2: In the remaining graph left to travel, certain edges you choose may get you stuck and prevent you from tracing all the edges without re-tracing (BRIDGES)

·  The concept of a bridge occurs in the yet-to-be-traveled portion of a graph (REMAINING GRAPH)

STEPS / Euler Circuit / Euler Path
1: EXISTENCE – Determine the type of Euler Graph? / Graph is connected and has NO ODD vertices
(Check the degree of all vertices) / Graph is connected and has EXACTLY TWO odd vertices
(Check the degree of all vertices)
2: STARTING VERTEX / Choose any vertex unless given a specific starting vertex in a problem
For an Euler Circuit, any vertex can be the start and the end for the circuit. / Choose either of the odd vertices
For an Euler Path, only the two odd vertices can be the start and end.
3: INTERMEDIATE STEPS – Tracing edges to find an Euler Path or Circuit / Label/Indicate the edges you have already traveled by numbering them in order.
In the remaining graph,
First, ALWAYS choose an unused (untraced or untraveled) edge that is NOT A BRIDGE at your current vertex.
Finally, ONLY choose a BRIDGE if it is the ONLY OPTION at your current vertex.

EXAMPLES OF FLEURY’S ALGORITHM:

·  Determine if each graph has an Euler PATH or CIRCUIT or None

·  Find the Euler Path or Circuit by NUMBERING EDGES

·  In an Euler Circuit pick vertex A as your start

·  In an Euler Path pick the odd vertex as start.