Winston-Salem/Forsyth County Schools / Front Page



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

• Two Important Basic Questions:

o Existence: Is an actual route even possible?

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

Special Case of Routing Problem:

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

• Route is called an exhaustive route.

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:

Set Notation: Empty Set: { }, has nothing in it

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 ________________, but still represent the _____ ___ relationships

• SPACIALLY: Can you stretch or drag parts of one graph to look like another.

• BOTH graphs can be labeled to have the _______________ VERTEX and EDGE SET

1) 2)

Which of the following graphs are the SAME GRAPH?

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

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

• In a path, each 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:

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.

• The connected parts of a disconnected graph are 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.

• An edge that is also the ONLY PATH between the two vertices.

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

Example Graph #1: Example Graph #2:

Bridge Practice: Identify the bridge in Figure #1 and Figure #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: Use the dot given as your start. Identify if the following drawings are closed, open, or neither type of unicursal tracing. (Hint: It may be more helpful to number rather than trace edges)

FURTHER CLASSIFICATION OF UNICRUSAL TRACINGS WITH GRAPH TERMINOLOGY:

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

2) What additional characteristic does a unicursal tracing have that we haven’t discussed in defining a path and circuit?

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.

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) FAMILIARITY and 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: The figure is a map of a neighborhood.

EDGES = __________________

VERTICES = _______________________

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

Example #4: The figure is a map of a neighborhood

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

|#2 |A = |A = |A = |A = |A = E = |

| | | | | | |

| |B = |B = |B = |B = |B = F = |

| | | | | | |

| |C = |C = |C = |C = |C = |

| | | | | | |

| |D = |D = |D = |D = |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 type of vertex can you start and end at? |

| | |

| | |

| | |

|What do all vertices have in common? |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 ___________________________ 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 = |A = B = C = |A = B = |

| | | | |

| |E = F = G = |D = E = F = |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 |Graph is connected and has NO ODD vertices |Graph is connected and has EXACTLY TWO odd vertices |

|Euler Graph? |(Check the degree of all vertices) |(Check the degree of all vertices) |

|2: STARTING VERTEX |Choose any vertex unless given a specific starting vertex in a |Choose either of the odd vertices |

| |problem | |

| | |For an Euler Path, only the two odd vertices can be the start |

| |For an Euler Circuit, any vertex can be the start and the end |and end. |

| |for the circuit. | |

|3: INTERMEDIATE STEPS – Tracing edges|Label/Indicate the edges you have already traveled by numbering them in order. |

|to find an Euler Path or Circuit | |

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

Section 5.7: Eulerizing Graphs

Routing Problems: If you can’t travel every edge once (No Euler Circuit or Path in graph), then you need to retrace some edges to meet the exhaustive requirement.

NEW GOAL: is to find an optimal route that has the least number of edge re-crossings (RETRACING).

Eulerization of a Graph: The process of creating a graph that will have an EULER CIRCUIT by turning odd vertices into even vertices by adding “duplicate” edges in strategic places to the original graph.

PROCESS of EULERIZING a GRAPH: Create a graph that has an Euler Circuit

1) IDENTIFY all the odd vertices (circle)

2) Pick any two odd vertices, and “duplicate” the shortest path between them by adding MULTIPLE EDGES along that path.

a. “DUPLICATE”: copy an existing edge by making multiple edges from original edge set

b. DO NOT Create a New Edge that wasn’t part of the original graph’s edge set

3) If more than 2 odd vertices remain after Step 2 is completed, find and duplicate the shortest path b/w pairs of the remaining odd vertices until No Odd Vertices Remain.

4) Try for OPTIMAL EULERIZATION.

Least Number of Multiple Edges, if possible (Always greater than or equal to half # of odd vertices)

5) Fleury’s Algorithm to find the ACTUAL Euler Circuit on this new graph.

Semi- Eulerization Graph: Creating an EULER PATH in a graph by turning odd vertices into even vertices by adding “duplicate” edges in strategic places and leaving two key vertices as odd (departure and arrival)

PROCESS of SEMI-EULERIZATION: Create a graph with an Euler path

1) Identify all the odd vertices

2) Pick any two odd vertices, and “duplicate” the shortest path between them by adding MULTIPLE EDGES along that path.

3) If more than 2 odd vertices remain after Step 2 is completed, find and duplicate the shortest path b/w pairs of the remaining pairs odd vertices until Start and End Vertices Remain.

a. START and END VERTEX must remain ODD, but more edges can be added to them to make larger odd degree

4) Try to create an OPTIMAL SEMI-EULERIZATION.

5) Fleury’s Algorithm to find the Euler Path.

EXAMPLES: SEMI-EULERIZING GRAPH

EXAMPLES: EULERIZING GRAPH

HOMEWORK: pp. 188-190 #27, 33, 34, 41, 42, 43

-----------------------

B

A

C

E

D

E

M

A

B

D

C

R

Q

N

P

O

A

B

C

D

E

F

U

V

W

X

Y

Z

E

A

B

B

A

D

D

C

Vertex Set: A, B, C, D, E,

Edge Set:

Vertex Set: A, B, C, D,

Edge Set:

A

B

C

D

E

A

B

C

D

A

B

A

B

C

D

E

C

D

A

B

C

D

E

Figure #1

B

H

S

J

W

K

Figure #2

A

P

S

U

T

R

B

C

D

E

F

V

Y

X

W

A

A

A

A

A

A

B

B

B

B

B

C

C

C

C

C

D

D

D

D

D

E

F

C

B

B

A

C

A

D

C

B

G

F

E

D

A

E

D

F

GRAPH #1:

GRAPH #2:

A

B

C

D

E

F

G

A

B

C

D

E

F

G

H

GRAPH #4:

GRAPH #3:

A

B

C

D

E

F

A

B

C

D

F

G

GRAPH #5:

GRAPH #6:

A

C

B

D

E

F

A

B

C

D

F

E

G

H

I

J

K

L

GRAPH #7:

GRAPH #8:

G

E

F

F

P

I

L

N

M

O

K

J

D

C

B

H

A

B

A

C

E

GRAPH #10:

B

A

C

D

E

GRAPH #9:

B

C

B

A

GRAPH #11:

P

O

N

M

L

K

J

I

H

F

G

E

D

D

E

F

G

F

A

C

D

G

A

B

C

D

F

E

G

H

I

J

K

L

A

B

C

D

E

F

A

B

C

D

E

F

G

START

END

START

START

END

END

START

END

START

END

END

START

C

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download