HAMILTON CIRCUIT AND PATH WORKSHEET



6.1 HAMILTON CIRCUIT AND PATH WORKSHEET

Use extra paper as needed.

For each of the following graphs:

1) Find ALL Hamilton Circuits starting from vertex A.

Hint: Mirror images (reverse) counts as a different circuit

2) Are there any edges that must always be used in the Hamilton Circuit?

3) Find a Hamilton Path from vertex C to E.

a. If it’s not possible, give an explanation.

DOES A HAMILTON PATH AND/OR CIRCUIT EXIST IN GENERAL?

For each of the following graphs: Use any vertex to START and/or END

1) Find a Hamilton Path. If it does not exist, then give a brief explanation.

2) Find a Hamilton Circuit. If it does not exist, then give a brief explanation.

6.1 HAMILTON CIRCUIT AND PATH WORKSHEET SOLUTIONS

For each of the following graphs:

4) Find all Hamilton Circuits that Start and End from A.

a. If it’s not possible, give an explanation.

5) Are there any edges that must always be used in the Hamilton Circuit?

6) Find a Hamilton Path from C to E.

a. If it’s not possible, give an explanation.

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

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

| |Note: B and C have degree two so they must use those |A, C, D, E, B, A |A, E, D, C, B, A |

| |two edges |A, C, B, D, E, A |A, E, C, D, B, A |

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

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

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

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

|2 |AB, BE, CD, CA |NONE |AE, AB |

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

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

For each of the following graphs:

3) Find a Hamilton Path.

a. If it does not exist, then give a brief explanation.

4) Find a Hamilton Circuit.

a. If it does not exist, then give a brief explanation.

1) path exists 1) Path exists 1) path exists

2) No circuit because a bridge exists 2) No circuit because a bridge exists 2) circuit exists

1) Not possible 1) Possible 1) Possible 1) Possible

2) Not possible 2) Possible 2) Not Possible 2) Possible

4 degree 2 vertices left degree 2 vertices

all share 2 adjacent share adjacent vertex

vertices

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

A

B

C

D

E

A

B

C

D

E

GRAPH 1

GRAPH 2

GRAPH 3

A

C

D

E

B

GRAPH 2

GRAPH 1

C

B

D

C

B

A

A

G

D

E

F

H

F

E

GRAPH 5

A

E

F

B

C

D

GRAPH 7

A

B

C

D

E

F

G

GRAPH 4

A

D

E

B

C

F

GRAPH 3

A

B

C

D

E

GRAPH 6

A

B

C

D

E

F

G

H

A

B

C

D

E

A

B

C

D

E

GRAPH 1

GRAPH 2

GRAPH 3

A

C

D

E

B

GRAPH 3

GRAPH 2

GRAPH 1

GRAPH 6

GRAPH 5

GRAPH 7

GRAPH 4

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

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

Google Online Preview   Download