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.
•By Definition:
must touch every vertex “can touch more than once depending on degree” / •HAMILTON = Touch each VERTEX exactly one time (enter/ leave once).
•By Definition:
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 PATH / NO / YES / NO / NO / YES / NO
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:
Follows the SAME rotation order for a circuit, but with a different start. / DISTINCT Hamilton Circuits:
A different order of vertices (Left to Right) from the same starting vertex. (reverse order counts)
B, C, D, A, B

C, D, A, B, C

D, A, B, C, D / A, D, C, B, A (reverse order)
A, D, B, C, A AND reverse = A, C, B, D, A
A, B, D, C, A AND reverse = A, C, D, B, A

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

A, B, C, D, E, F, G, A
A, B, E, D, C, F, G, A
A, F, C, D, C, B, G, A
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.

Notation:KN =a complete graph of N vertices

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

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

Does a complete graph have to be connected?
YES; “every pair of vertices connected by an edge”

Is a complete graph allowed to have loops?
NO; “Distinct (Different) Vertices only”

Is a complete graph allowed to have multiple edges?

NO; exactly “one edge”

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 = 2K4: Degree = 3K5: Degree = 41 Less than the # of vertices

Degree = N - 1

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

EDGESTOTAL DEGREE

K3: EDGES =36 = 3*2

K4: EDGES =612 = 4*3

K5: EDGES = 1020 = 5*4

K6: EDGES = 1530 = 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)

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 /

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?
2 /

1) How many Hamiltonian circuits does it have?

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:

K4:

K5:

K6:

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 KNhas 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 KNhas 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 K12is x and the number of edges of K13is 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.

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

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

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

How many vertices are in the KN graph? 7 VERTICES

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

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 assignedto them

(NOT DRAWN TO SCALE ALWAYS)

Weights: number for each edge
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 – AA-B-D-C- A

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

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

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

12+15+17+20 = 64 BLOCKS8 +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 Buses2) Package Deliveries: UPS or FedEx Delivery Truck

3) Running Errands around Town4) 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, B, D, C, A

A, C, B, D, A

A, D, C, B, A

A, C, D, B, A

A, D, B, C, A

13 + 9 + 14 + 15 = 51

13 + 16 + 14 + 12 = 55

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

AB = 12

AC = 20

AD = 8

BA = 12

BC = 20

BD = 15

CA = 20

CB = 20

CD = 17

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

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

Draw the following complete weighted graph described by table:

FIND THE NEAREST NEIGHBOR SOLUTION STARTING AT D:

D (1) E (6) A (3) B (5) C (6) D = 21

The following Complete Weighted Graph can also be represented by the table:

Does BRUTE FORCE seem practical here?

NO; (7-1)!= 720 POSSIBLE HAMILTON CIRCUITS

Start at Vertex A – Find the NEAREST NEIGHBOR SOLUTION:
(Use table or graph)

A – (15) – F – (13) – G – (28) – C – (30) – B – (60) – D – (20) - E – (35) - A = 201

HOMEWORK: pp. 223 – 225 # 29 - 31, 33, 35

Section 6.7: Repetitive Nearest-Neighbor Algorithm

The Nearest Neighbor Algorithm is an EFFICIENT but NOT always ACCURATE algorithm.

Is there a way we can improve it because we like its efficiency? Compare from different starting spots

The REPETITIVE Nearest-Neighbor Algorithm:

Perform the Nearest-Neighbor Algorithm for everyvertex of the graph as the starting vertex.

Compare circuits and CHOOSE the circuit with least weight of all the options.
If needed, Re-order (shift) that Hamilton Circuit to have the DESIGNATED START vertex first.

Re-ordered (shifted) circuits have the same weight but change its starting vertex

EXP #1:Perform the nearest neighbor algorithm for start of A.

A: A, B, D, C, A = 9 + 13 + 11+ 15 = 48

B: B, A, D, C, B = 9 + 10 + 11 + 17 = 47

C: C, D, A, B, C = 11 + 10 + 9 + 17 = 47

D: D, A, B, C, D = 10 + 9 + 17 + 11 = 47

Final Answer: A,B,C,D,A or A,D,C,B,A = 47

EXAMPLE #2:Label the graph and complete the Repetitive nearest neighbor algorithm for a start of C.

A / B / C / D / E
A / $185 / $119 / $152 / $133
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.

/ G

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 edgein the graph and as long as

(a)it does not close a circuit and

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

(c)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