Opening the book…
For the following exercises, use the figure to determine whether the sequence of vertices in the given graph is a Hamilton path, an Euler trail, both, or neither.
Graph G: f → b → g → e → d → c
Graph G: g → b → f → c → d → e
Graph G: f → b → g → d → f → c → d → e → g
Graph W: v → w → r → s → t → o → q
Graph W: s → r → w → v → q → o → t
Graph N: h → i → k → n → j → h
Graph N: n → i → h → j → m
Graph N: m → j → h → i → k → n → i → j → k
For the following exercises, use the figure to explain why the given sequence of vertices does not represent a Hamilton path.
Graph A: t → s → v → u → x → w → y → z
Graph B: w → x → r → u → z → y → s → t → u → v
Graph C: s → u → w → v → t
Graph D: r → → t → q → u → t → x → v → w → x → z → y
For the following exercises, use the figure to find a path that fits the description or indicate which scenario from the figure makes it impossible.
A Hamilton path in Graph H that begins at vertex c and ends at vertex e.
A Hamilton path in Graph Q that begins at vertex n and ends at vertex h.
A Hamilton path in Graph H that begins at vertex c and ends at vertex g.
A Hamilton path in Graph Q that begins at vertex m and ends at vertex j.
A Hamilton path in Graph H that begins at vertex g.
A Hamilton path in Graph Q that begins at vertex i.
A path between n and j in Graph Q that is NOT a Hamilton path, and explain why it is not a Hamilton path.
A path between a and c in Graph H that is NOT a Hamilton path, and explain why it is not a Hamilton path.
In chess, a knight can move in any direction, but it must move two spaces then turn and move one more space. The eight possible moves a knight can make from a given space are shown in the figure.
A knight’s tour is a sequence of moves by a knight on a chessboard (of any size) such that the knight visits every square exactly once. If the knight’s tour brings the knight back to its starting position on the board, it is called a closed knight’s tour. Otherwise, it is called an open knight’s tour. Determine if the Knight’s tour shown in the figure is a Hamilton path, an Euler trail, or both, for the graph of all possible knight moves on an eight-by-eight chess board in which the vertices are spaces on the board and the edges indicate that the knight can move directly from one space to the other. Explain your reasoning.
Recall from the section Euler Circuits, as part of the Camp Woebegone Olympics, there is a canoeing race with a checkpoint on each of the 11 different streams as shown in the figure. The contestants must visit each checkpoint.
Draw a graph in which the vertices represent checkpoints, and an edge indicates that it is possible to travel from one checkpoint to the next without passing through another checkpoint.
Find a Hamilton path beginning at vertex A and ending at vertex E.
What does this Hamilton path represent in the context of the race?
The figure shows a map of zoo exhibits A through P. Use it to answer each question.
Draw a graph to represent the routes through the zoo in which the edges represent walkways and the vertices represent exhibits. Two vertices are connected if a person can walk between the exhibits they represent without passing another exhibit.
Use the graph you created to find a route that begins at exhibit M, ends at exhibit J, and visits each exhibit exactly once.
12.8.1: Exercises is shared under a not declared license and was authored, remixed, and/or curated by LibreTexts.
The book could not be loaded just now.