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.
(a)
To find:
Three Hamilton circuits for given graph.
Answer to Problem 1E
Solution:
The Hamilton circuit are
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
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
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
Conclusion:
Thus, the Hamilton circuits are
(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
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
Conclusion:
Thus, a Hamilton path that starts at A and ends at B is
(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
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
Conclusion:
Thus, a Hamilton path that starts at D and ends at F is
Want to see more full solutions like this?
Chapter 6 Solutions
Excursions in Modern Mathematics (9th Edition)
Additional Math Textbook Solutions
The Heart of Mathematics: An Invitation to Effective Thinking
Finite Mathematics with Applications In the Management, Natural, and Social Sciences (12th Edition)
Discrete Mathematics and Its Applications ( 8th International Edition ) ISBN:9781260091991
Finite Mathematics (11th Edition)
Probability and Statistics for Engineers and Scientists
- Which of the graphs has a Hamiltonian circuit? a. graphs 1 and 2 onlyb. graph 2 onlyc. graph 1 onlyd. graphs 2 and 3 onlye. graph 3 onlyf. graphs 1, 2, and 3arrow_forwardRefer to the figure below. a. Find a closed path of length 4 starting at vertex v2. b. Find a cycle of length 5 starting at vertex V1. c. Find a circuit that is not a cycle at vertex V4. VI V6 V5 V2 VA V 3arrow_forwardConsider the following graph: Vz V, e, Vz es es Vs eu 1. Please give a walk from v, to v4 that is not a trail. 2. Please give a path from vị to V4. 3. Please give a closed walk from v4 to v4 that is not a circuit. 4. Please give a simple circuit from vi to v1.arrow_forward
- Linear Algebra: A Modern IntroductionAlgebraISBN:9781285463247Author:David PoolePublisher:Cengage LearningAlgebra: Structure And Method, Book 1AlgebraISBN:9780395977224Author:Richard G. Brown, Mary P. Dolciani, Robert H. Sorgenfrey, William L. ColePublisher:McDougal Littell