Chapter 5 Euler Circuits



Chapter 6 Traveling Salesman Problem

ESSENTIAL QUESTIONS:

Section 6.1: How does Hamilton’s Circuits and Paths compare to Euler’s?

Section 6.2: What is a complete graph?

Section 6.3: What do the Traveling Salesman Problems (TSPs) use weighted graphs?

Section 6.4: What are simple strategies for solving TSPs?

Section 6.5: How does the Brute-Force and Nearest –Neighbor Algorithms solve TSPs?

Section 6.6: What is an approximate algorithm?

Section 6.7: How does the Repetitive Nearest – Neighbor Algorithm improve your ability to solve TSPs?

Section 6.8: How does the Cheapest-Link Algorithm differ from the Nearest-Neighbor Algorithm?

WORD WALL:

Brute-Force Algorithm

Cheapest-Link Algorithm

Complete Graph

Weight

Hamilton Circuit

Hamilton Path

Inefficient Algorithm

Nearest-Neighbor Algorithm

Repetitive Nearest-Neighbor Algorithm

Traveling Salesman Problem (TSP)

Weighted Graph

Extra Review/ Possible Homework:

6.1 = pp. 221 - 2 # 2, 4, 6, 7, 10, 11

6.2 = p 223 # 25 – 28

6.3 = pp. 222 – 3 # 13 – 16

6.4/6.5 = pp. 223 – 225 # 29 - 31, 33, 35

6.7 = p. 225 #37 – 39, 41

6.8 = pp. 225 - 6 #43-45, 47

Section 6.1: Hamilton Circuits and Hamilton Paths

|EULER CIRCUITS AND PATHS |HAMILTON CIRCUITS AND PATHS |

|EULER = touch each EDGE of a graph exactly one time. |HAMILTON = Touch each VERTEX exactly one time (enter/ leave once). |

| | |

|By Definition: |By Definition: |

|must touch every vertex “can touch more than once depending on degree” |Doesn’t require touching every edge |

HAMILTON Circuits/Paths VERSUS EULER Circuits/Paths

For each of the following graphs, use our definitions of Hamilton and Euler to determine if circuits and paths of each type are possible.

| |Graph 1 |Graph 2 |Graph 3 |Graph 4 |Graph 5 |Graph 6 |

|EULER CIRCUIT |YES |NO |NO |YES |NO |NO |

|HAMILTON PATH |YES |YES |YES |YES |NO |YES |

|HAMILTON CIRCUIT |YES |NO |YES |NO |NO |NO |

What do you notice about the relationship between a graph having an Euler Circuit or Path and having a Hamilton Circuit of path?

There is no relationship

IN GENERAL, THERE ARE NO THEOREMS TO DETERMINE IF A GRAPH HAS A HAMILTON PATH OR CIRCUIT.

HELPFUL HINT:

#1: FOR HAMILTON CIRCUITS/ PATHS, VERTICES OF DEGREE 1 OR 2 ARE VERY HELPFUL BECAUSE THEY REPRESENT REQUIRED EDGES TO REACH THAT VERTEX.

#2: EXAMPLE: Hamilton Circuit = A, B, C, D, A

|SHIFT/SAME Hamilton Circuits: |DISTINCT Hamilton Circuits: |

|Follows the SAME rotation order for a circuit, but with a different start. |A different order of vertices (Left to Right) from the same starting vertex. |

| |(reverse order counts) |

|B, C, D, A, B |A, D, C, B, A (reverse order) |

|C, D, A, B, C |A, D, B, C, A AND reverse = A, C, B, D, A |

|D, A, B, C, D |A, B, D, C, A AND reverse = A, C, D, B, A |

EXAMPLE #1: List all possible Hamiltonian circuits in the following graph

1. A, B, C, D, E, F, G, A

2. A, B, E, D, C, F, G, A

3. A, F, C, D, C, B, G, A

4. A, F, E, D, C, B, G, A

REVERSE EACH ONE OF THESE 4 CIRCUITS

What about the Hamiltonian circuits that start at B, C, D, etc.?

Well, since such a circuit must pass through all of the vertices it doesn’t matter which vertex we start with.

Related to the idea of shifts of circuits.

EXAMPLE #2:

a) Find a Hamiltonian path that begins at A and ends at E.

b) Find a Hamiltonian circuit that starts at A and ends with the pair of vertices E, A.

c) Find a Hamiltonian path that begins at F and ends at G.

a) A, F, B, C, G, D, E

b) A, F, B, C, G, D, E, A

c) F, B, C, E, A, D, G

F, A, E, B, C, D, G

Example 3: The following graph has no Hamiltonian circuits or paths--why not?

4 bridges exist = can’t have a circuit; No path possible because multiple vertices of degree 1

EXAMPLE #4:

a) Find all Hamiltonian circuits that starts at A.

b) Find all Hamiltonian circuits that starts at D.

c) Explain why your answers in a and b must have the same number of circuits.

a) A, C, F, D, E, B, A

A, D, F, E, B, C, A

A, D, E, F, C, B, A (REVERSE ORDER as well)

b) Re-order answers in part a

c) Re-ordering concept

HOMEWORK: pp. 221 - 222 # 2, 4, 6, 7, 10, 11

Section 6.2: Complete Graphs

EXAMPLE PUT 6 OR 8 DOTS ON WHITEBOARD AND START CONNECTING THEM AND ASK STUDENTS TO DESCRIBE HOW I AM MAKING THE GRAPH: “ONE DOT IS CONNECTED TO EVERY OTHER DOT” TO START DEFINITION

COMPLETE GRAPH: A graph in which every pair of distinct vertices is joined by exactly one edge.

o Notation: KN = a complete graph of N vertices

EXAMPLES OF COMPLETE GRAPHS for 3, 4, and 5 vertices:

[pic]

Use the definition of a complete graph to answer the following questions:

1. Does a complete graph have to be connected?

2. YES; “every pair of vertices connected by an edge”

3. Is a complete graph allowed to have loops?

NO; “Distinct (Different) Vertices only”

4. Is a complete graph allowed to have multiple edges?

NO; exactly “one edge”

5. Can different vertices have different degree?

NO; each vertex must be connected all remaining vertices

What is the DEGREE of each VERTEX for N vertices?

K3: Degree = 2 K4: Degree = 3 K5: Degree = 4 1 Less than the # of vertices

Degree = N - 1

How many EDGES are in KN (complete graph of N vertices)?

EDGES TOTAL DEGREE

K3: EDGES = 3 6 = 3*2

K4: EDGES = 6 12 = 4*3

K5: EDGES = 10 20 = 5*4

K6: EDGES = 15 30 = 6*5

What is the relationship between edges and degrees?

Euler’s Sum of Degree Theorem:

(total # of degrees) = 2 * (# of edges)

N(N-1) = 2 * (# of edges)

[pic]number of edges in KN

• Where have you seen this formula before? Chapter 1: the number of pairwise comparisons.

DEGREE and VERTICES are consecutive numbers.

SUMMARY OF COMPLETE GRAPH INFORMATION

|Complete Graph |Number of Vertices |Degree of Each Vertex |Number of Edges |

|KN |N |N – 1 |[pic] |

Connected Graph, No Loops, No Multiple Edges

|K3= Complete Graph of 4 Vertices |K4 = Complete Graph of 4 Vertices |

|1) How many Hamiltonian circuits does it have? |1) How many Hamiltonian circuits does it have? |

|2 |6 |

If we were to answer the same questions for K5 we would find the following:

1) How many Hamiltonian circuits does it have?

(Do you notice any possible relation in how we answered this question for K3 and K4 that might help you here?)

(5 - 1) (5 - 2) ( 5 - 3) (5 - 4) = (4)(3)(2)(1) = 24 (see page 202 for exact circuits)

How many DISTINCT HAMILTON CIRCUITS are in KN?

|Complete Graph |Vertices |Hamilton Circuits |

|K3: |3 |2 |

|K4: |4 |6 |

|K5: |5 |24 |

|K6: |6 |120 |

(N – 1)! = (Degree) != Distinct Hamilton Circuits in KN.

Calculator Command Reminder: [MATH] – [PRB] – [4:!]

INDEPENDENT PRACTICE: Apply the Properties of Complete Graphs

1) How many edges are there in K20? 20(19)/2 = 190 edges

2) How many distinct Hamilton Circuits exist in K10? (10 – 1)! = 9! = 362880

3) How many vertices are in the K50 graph? N = 50

4) What is the degree of every vertex in K200? Degree = 200-1 = 199

5) How many distinct Hamilton Circuits exist in K22?

(22 – 1)! = 21! Or 5.109094217E19

6) How many edges are there in K32? Edges = (32)(32 – 1)/2 = 496 edges

7) What is the degree of every vertex in K15? Degree = 15 – 1 = 14

8) If KN has 120 distinct Hamiltonian circuits then what is N?

N = 6

Trial and Error: Divide 120 by consecutive numbers starting with 2

Add one to last number used = Number of vertices

9) If KN has 55 edges then what is N?

N = 11

55 = (N)(N-1)/2;

HINT: square root trick of DOUBLE EDGES round up = N and round down = N -1

10) If the number of edges of K12 is x and the number of edges of K13 is y, what is the values of y - x?

(13)(12)/2 - (12)(11)/ 2 = (12/2) (13-11) = 12

11) For each of the following cases find the value of N.

a. KN has 5040 distinct Hamilton Circuits. 5040 = 7!; N = 7 + 1 = 8

b. KN has 66 edges. 66 = 12*11/2; N = 12

c. KN has 80,200 edges. 80,200 = 401*400/2; N = 401

12) If KN has 362,880 distinct Hamilton Circuits, then… 362,880 = 6!; N = 7

a. How many vertices are in the KN graph? 7 VERTICES

b. What is the degree of each vertex are in the KN graph? 7 -1 = 6

c. How many edges are in the KN graph?7*6/2 = 21 edges

Section 6.3: Traveling Salesman Problems

WEIGHTED GRAPH: Any graph whose edges have numbers associated or assigned to them

(NOT DRAWN TO SCALE ALWAYS)

o Weights: number for each edge

o Examples of Weights: distance, time, cost…

Complete Weighted Graph: Complete graph that has weights associated with it

TRAVELING SALESMAN PROBLEMS:

From home, the traveling salesman must visit different destinations to sell goods and return home. This is essentially finding a Hamilton Circuit.

GOAL: Try to find the cheapest, most efficient, optimal route that is a Hamilton circuit for a given graph (find the least total weight)

Example – The Simpsons: Homer Simpson he has to run errands at the Kwik-E-Mart, the Retirement Home and Moe`s. Assuming that he wants to begin and end his day at home find the route that will allow him to get back to napping as soon as possible.

The numbers will represent the number of blocks between each destination.

When we place values like this on the edges of a graph we refer to them as the weights of the edges.

What if Homer preferred going to see Grandpa first to get it out of the way?

A – B – C – D – A A-B-D-C- A

12 + 20 + 17 + 8 = 57 BLOCKS 12+15+17+20 = 64 BLOCKS

What if Homer preferred going to the KWIK-E-MART last?

A-B-D-C- A A – D – B – C – A

12+15+17+20 = 64 BLOCKS 8 +15 + 20 + 20 = 63 BLOCKS

Traveling Salesman Problem Steps:

1) Create graph models

2) Apply weights to these models

3) Find optimal Hamilton Circuits. (Not Always a practical statement)

REAL-LIFE EXAMPLES:

1) Routing School Buses 2) Package Deliveries: UPS or FedEx Delivery Truck

3) Running Errands around Town 4) Planning a road trip

5) Grocery Shopping: Planning which aisles you need to go down

HOMEWORK: pp. 222 – 223 # 13 – 16

Section 6.4 and 6.5: Simple Algorithms for Solving Traveling Salesman Problems

Strategy #1: BRUTE FORCE (Exhaustive Search)

|Circuit |Mirror Image |Weight |

|A, B, C, D, A |A, D, C, B, A |13 + 9 + 14 + 15 = 51 |

| | | |

|A, B, D, C, A |A, C, D, B, A |13 + 16 + 14 + 12 = 55 |

| | | |

|A, C, B, D, A |A, D, B, C, A |12 + 9 + 16 + 15 = 52 |

|BRUTE-FORCE ALGORITHM |

|Step 1: Make a list of ALL distinct Hamilton circuits of the graph from ONE starting vertex |

| |

|Step 2: Calculate its TOTAL WEIGHT for each circuit. |

| |

|Step 3: Choose an OPTIMAL circuit. (There is always more than one optimal circuit because of mirror-images) |

| |

|PRO: Guarantee Optimal Hamilton Circuit |

| |

| |

|CON: INEFFICIENT ALGORITHM |

|# steps needed to carry out algorithm grows disproportionately with the size of population (vertices) |

|ie TAKES A LOT OF TIME the more vertices/ edges there are |

STRATEGY #2: NEAREST – NEIGHBOR ALGORITHM

From the start vertex, go to the vertex that is the shortest to get to. From each new vertex go to the next new city that is the shortest to get to. When there are no more new vertices to go to, go to the starting vertex.

A (12) C (9) B (16) D (15) A = 52

|NEAREST-NEIGHBOR ALGORITHM |

|Start: Start at the designated starting vertex (home). If there is no designated starting vertex, pick any vertex. |

| |

|Step 1: From the starting vertex go to its NEAREST NEIGHBOR (vertex that is the smallest weight away) |

| |

|Middle Steps: From each vertex go to its nearest neighbor that hasn’t already been visited. (smallest remaining weight of possible vertices) Keep doing this until |

|all the vertices have been visited. |

| |

|Last Step: From the last neighbor (vertex) RETURN to the starting vertex (home). |

| |

|PRO: EFFICIENT ALGORITHM |

|Amount of computational effort required to implement it grows in some reasonable proportion with the size of population (vertices) |

|ie WORKS FAST/ LESS TIME CONSUMING TO COMPLETE METHOD |

| |

|CON: Not an optimal Algorithm; Answers won’t always be the OPTIMAL, but relatively close to being the best possible way |

A weighted Graph may also be represented as table. Vertices along the first row and column. Weights on the interior of table.

| |A |B |C |D |

|A | |AB = 12 |AC = 20 |AD = 8 |

|B |BA = 12 | |BC = 20 |BD = 15 |

|C |CA = 20 |CB = 20 | |CD = 17 |

|D |DA = 8 |DB = 15 |DC = 17 | |

Observations:

1) Diagonal is blank because NO LOOPS exist.

2) Upper Right Triangle and Lower Left Triangle are Identical Numbers

a. Represent Same Edges, but are in different order of starting and ending vertices

Draw the following complete weighted graph described by table:

| |A |B |C |D |E |

|B |$185 | |$121 |$150 |$200 |

|C |$119 |$121 | |$174 |$120 |

|D |$152 |$150 |$174 | |$199 |

|E |$133 |$200 |$120 |$199 | |

EXAMPLE #3: Perform repetitive nearest neighbor algorithm for a start of B.

ABCDEFGA755028351522B753060806550C503040483528D286040203029E358048204032F156535304013G225028293213

Final: shift A Answer

B, D, E, A, F, G, C, B

B, C, G, F, A, E, D, B

HOMEWORK: p. 225 #37 – 39, 41

Section 6.8: Cheapest-Link Algorithm

GOAL: Piece together a Hamilton circuit by individual edges or “LINKS” of graph trying to choose the smallest or “cheapest” weights first.

The Cheapest-Link Algorithm for N Vertices:

Step #1: Pick the edge with the smallest weight first. Mark the edge (or otherwise note that you have chosen it).

Smallest weight ANYWHERE on the graph

Step #2: Pick the next ‘cheapest’ edge anywhere in the graph. Mark or note it.

Step #3, …, N-1:Continue picking the ‘cheapest’ available edge in the graph and as long as

it does not close a circuit and

it does not result in three edges coming out of a single vertex. (DEGREE = 2)

Ties can be broken at random and don’t break the two rules

HINT: Draw out the edges chosen helps to double check what is and is not available.

Step #N: Connect the last two vertices to close the circuit

(you are forced to choose this edge so no need for “cheapest”)

REORDER CIRCUIT TO THE NECESSARY STARTING VERTEX (N Vertices = N edges chosen for circuit)

EXAMPLE #1: Start at G

When table only, draw links to visualize circuit.

START IT AT G: G – F – A – D – E – C – B – G = 13 + 15 + 28 + 20 + 48 + 30 + 50 = 204

EXAMPLE #2: Start at B

HOMEWORK: pp. 225 - 6 #43-45, 47

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

|A |A, B, C, A |

| | |

|B | |

| | |

|C | |

| | |

|D | |

| | |

|A | |

| | |

|B | |

| | |

|C | |

| | |

|D | |

| | |

|F | |

| | |

|E | |

| | |

|G | |

| | |

| | |

| | |

|F | |

| | |

|A | |

| | |

|B | |

| | |

|C | |

| | |

|D | |

| | |

|G | |

| | |

|E | |

| | |

|A | |

| | |

|B | |

| | |

|C | |

| | |

|D | |

| | |

|E | |

| | |

|F | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

|K3 | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

|K4 | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

|K5 | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

|K3 | |

| | |

|A | |

| | |

|B | |

| | |

|C | |

| | |

|1 | |

|2 |A, C, B, A |

|1 |A, B, C, D, A |

|2 |A, B, D, C, A |

|3 |A, C, B, D, A |

|4 |A, C, D, B, A |

|5 |A, D, B, C, A |

|6 |A, D, C, B, A |

K4

A

B

C

D

12

8

20

17

15

20

A

B

C

D

13

15

9

14

16

12

A

B

C

D

12

8

20

17

15

20

A

B

C

D

| |A |B |C |D |E |

|B |$185 | |$121 |$150 |$200 |

|C |$119 |$121 | |$174 |$120 |

|D |$152 |$150 |$174 | |$199 |

|E |$133 |$200 |$120 |$199 | |

A

B

C

D

E

19

12

24

17

A – C = 119

E – C = 120

B – D = 150

A – D = 152

E – B = 200

741 = total cost

Start at D:

D, A, C, E, B, D or D, B, E, C, A, D = 741

29

27

19

21

9

Start at B:

B, A, E, C, D, B

B, D, C, E, A, B

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

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

Google Online Preview   Download