Page 728 - Discrete Mathematics and Its Applications

10.6 Shortest-Path Problems 707

A knight is a chess piece that can move either two spaces 62. Show that the graph representing the legal moves of a
horizontally and one space vertically or one space horizon- knight on an m × n chessboard, whenever m and n are
tally and two spaces vertically. That is, a knight on square positive integers, is bipartite.
(x, y) can move to any of the eight squares (x ± 2,y ± 1), 63. Show that there is no reentrant knight’s tour on an m × n
(x ± 1,y ± 2), if these squares are on the chessboard, as il- chessboard when m and n are both odd. [Hint: Use Exer-
lustrated here. cises 55, 58b, and 62.]
∗ 64. Show that there is a knight’s tour on an 8 × 8 chessboard.
[Hint: You can construct a knight’s tour using a method
invented by H. C.Warnsdorff in 1823: Start in any square,
and then always move to a square connected to the fewest
number of unused squares.Although this method may not
always produce a knight’s tour, it often does.]
65. The parts of this exercise outline a proof of Ore’s theo-
rem. Suppose that G is a simple graph with n vertices,
n ≥ 3, and deg(x) + deg(y) ≥ n whenever x and y are
nonadjacent vertices in G. Ore’s theorem states that under
these conditions, G has a Hamilton circuit.
a) Show that if G does not have a Hamilton circuit, then
A knight’s tour is a sequence of legal moves by a knight start-
ing at some square and visiting each square exactly once. A there exists another graph H with the same vertices
knight’s tour is called reentrant if there is a legal move that as G, which can be constructed by adding edges to G
takes the knight from the last square of the tour back to where such that the addition of a single edge would produce
the tour began. We can model knight’s tours using the graph a Hamilton circuit in H.[Hint: Add as many edges
as possible at each successive vertex of G without
that has a vertex for each square on the board, with an edge
producing a Hamilton circuit.]
connecting two vertices if a knight can legally move between
b) Show that there is a Hamilton path in H.
the squares represented by these vertices.
c) Let v 1 , v 2 ,..., v n be a Hamilton path in H. Show
56. Draw the graph that represents the legal moves of a knight that deg(v 1 ) + deg(v n ) ≥ n and that there are at most
ona3 × 3 chessboard. deg(v 1 ) vertices not adjacent to v n (including v n it-
self).
57. Draw the graph that represents the legal moves of a knight d) Let S be the set of vertices preceding each vertex adja-
ona3 × 4 chessboard.
cent to v 1 in the Hamilton path. Show that S contains
58. a) Show that finding a knight’s tour on an m × n chess- deg(v 1 ) vertices and v n /∈ S.
board is equivalent to finding a Hamilton path on the e) Show that S contains a vertex v k , which is adjacent
graph representing the legal moves of a knight on that to v n , implying that there are edges connecting v 1 and
board. v k+1 and v k and v n .
f) Show that part (e) implies that v 1 , v 2 ,..., v k−1 ,
b) Show that finding a reentrant knight’s tour on an
v k , v n , v n−1 ,..., v k+1 , v 1 is a Hamilton circuit in G.
m × n chessboard is equivalent to finding a Hamil-
Conclude from this contradiction that Ore’s theorem
ton circuit on the corresponding graph.
holds.
∗ 59. Show that there is a knight’s tour on a 3 × 4 chessboard. ∗ 66. Show that the worst case computational complexity ofAl-
gorithm 1 for finding Euler circuits in a connected graph
∗ 60. Show that there is no knight’s tour on a 3 × 3 chessboard.
with all vertices of even degree is O(m), where m is the
∗ 61. Show that there is no knight’s tour on a 4 × 4 chessboard. number of edges of G.

10.6 Shortest-Path Problems

Introduction

Many problems can be modeled using graphs with weights assigned to their edges. As an
illustration, consider how an airline system can be modeled. We set up the basic graph model
by representing cities by vertices and flights by edges. Problems involving distances can be
modeled by assigning distances between cities to the edges. Problems involving flight time can
be modeled by assigning flight times to edges. Problems involving fares can be modeled by