Chapter 6, Problem 1E

For the graph shown in Fig. 6-19,

a. find three different Hamilton circuits.

b. find a Hamilton path that starts at A and ends at B.

c. find a Hamilton path that starts at D and ends at F.

$Figure6-19$

To determine

(a)

To find:

Three Hamilton circuits for given graph.

Answer to Problem 1E

Solution:

The Hamilton circuit are $A,B,D,C,E,F,G,A$; $A,G,B,D,C,E,F,A$ and $A,D,B,E,C,F,G,A$.

Explanation of Solution

Given:

The given figure is,

Approach:

A Hamilton circuit is the circuit that starts and ends at the same vertex and includes every other vertex of the graph only once.

Calculation:

Let’s start with vertex A the options to go forward are vertices B, D, F, and G, go to vertex B. From vertex B the options to move further are C, D, E, and G, go to vertex D. From vertex D the option to go forward is vertex C. From vertex C the option to move forward to is E. From vertex E the option to move forward to is F. From vertex F the option to move forward to is G. From vertex G the option to move forward to is A.

The Hamilton circuit is $A,B,D,C,E,F,G,A$.

Let’s start with vertex A the options to go forward are vertices B, D, F, and G, go forward with vertex G. From vertex G the options to move further are B and F, go forward with vertex B. From vertex B the options to go forward are vertices C, D, and E, go to vertex D. From vertex D the option to move forward to is C. From vertex C the option to move forward to is E. From vertex E the option to move forward to is F. From vertex F the option to move forward to is A.

The Hamilton circuit is $A,G,B,D,C,E,F,A$.

Let’s start with vertex A the options to go forward are vertices B, D, F, and G, go forward with vertex D. From vertex D the options to move further are B and C, go forward with vertex B. From vertex B the options to go forward are vertex C and E, go to vertex E. From vertex E the option to move forward to is C. From vertex C the option to move forward to is F. From vertex F the option to move forward to is G. From vertex G the option to move forward to is A.

The Hamilton circuit is $A,D,B,E,C,F,G,A$.

Conclusion:

Thus, the Hamilton circuits are $A,B,D,C,E,F,G,A$; $A,G,B,D,C,E,F,A$; $A,D,B,E,C,F,G,A$.

To determine

(b)

To find:

A Hamilton path that starts at A and ends at B.

Answer to Problem 1E

Solution:

A Hamilton path that starts at A and ends at B is $A,G,F,E,C,D,B$.

Explanation of Solution

Given:

The given figure is,

Approach:

A Hamilton path is the path that includes every other vertex of the graph only once.

Calculation:

Let’s start with vertex A the options to go forward are vertices B, D, F, and G, go forward with vertex G. From vertex G the options to move further are B and F, go forward with vertex F. From vertex F the options to go forward are vertex C, E, and G, go to vertex E. From vertex E the option to move forward to are B and C, go to vertex C. From vertex C the option to move forward to are B and D, go to vertex D. From vertex D the option to move forward to is B.

The Hamilton path is $A,G,F,E,C,D,B$.

Conclusion:

Thus, a Hamilton path that starts at A and ends at B is $A,G,F,E,C,D,B$.

To determine

(c)

To find:

A Hamilton path that starts at D and ends at F.

Answer to Problem 1E

Solution:

A Hamilton path that starts at D and ends at F is $D,C,E,B,G,A,F$

Explanation of Solution

Given:

The given figure is,

Approach:

A Hamilton path is the path that includes every other vertex of the graph only once.

Calculation:

Let’s start with vertex D the options to go forward are vertices A, B, C, go forward with vertex C. From vertex C the options to move further are B, E and F, go forward with vertex E. From vertex E the options to go forward are vertex B and F, go to vertex B. From vertex B the option to move forward to are A and G, go to vertex G. From vertex G the option to move forward to are A and F, go to vertex A. From vertex A the option to move forward to is F.

The Hamilton path is $D,C,E,B,G,A,F$.

Conclusion:

Thus, a Hamilton path that starts at D and ends at F is $D,C,E,B,G,A,F$.