The remaining ones are
2, 1, 3, 4 cost = 2+6+1+4 = 13
2, 1, 4, 3 cost = 2+6+8+9 = 25
2, 3, 1, 4 cost = 2+3+5+4 = 14
2, 3, 4, 1 cost = 2+3+8+7 = 20
5. Here is a very simple example:
∙12
29
¸
6. Start by computing the sum of the numbers given. If is odd, stop
because the problem doesn’t have a solution. If is even, generate the
7. Generate a subset of vertices and check whether every pair of vertices
8. Generate a permutation of the elements given and check whether they
are ordered as required by comparing values of its consecutive elements.
9. The number of different positions of eight queens on the 8×8board is
equal to
10. a. Let be the sum of the numbers in each row of an ×magic square.
Letusaddallthenumbersinrows1through. We will get the following
equality:
11. a. Since the letter-digit correspondence must be one-to-one and there
are only ten distinct decimal digits, the exhaustive search needs to check
(10) = 10!(10 −)! possible substitutions, where is the number
of distinct letters in the input. (The requirement that the first letter of
a word cannot represent 0 can be used to reduce this number further.)
sum, even if increased by 1 because of the carry from the hundred column,
must be less than 20.) We will have to rely on some further insights into
specifics of the problem. The leftmost digits of the addends imply one of
Since we deal here with the case of no carry from the hundreds and E and
N must be distinct, the only possibility is a carry from the tens: 1 + E = N
andeitherN+R=10+E(iftherewasnocarryfromtherightmostcolumn)
or 1 + N + R = 10 + E (if there was such a carry). The first combination
leads to a contradiction: Substituting 1 + E for N into N + R = 10 + E, we
obtain R = 9, which is incompatible with the same digit already represented by
S. Thesecondcombinationof1+E=Nand1+N+R=10+Eimplies,
after substituting the first of these equations into the second one, R = 8. Note
Is this the only solution? To answer this question, we should pursue the
carry possibility from the hundred column to the thousand column (see above).
Then1+S+M=10+Oor,sinceM=1,S=8+O. ButS≤9, while 8 +
O≥10 since O ≥2. Hence the last equation has no solutions in our domain.
This proves that the puzzle has no other solutions.
36
Exercises 3.5
1. Consider the following graph.
f b
d a e
gc
a. Write down the adjacency matrix and adjacency lists specifying this
2. If we define sparse graphs as graphs for which ||∈(||),whichim–
plementation of DFS will have a better time efficiency for such graphs,
the one that uses the adjacency matrix or the one that uses the adjacency
lists?
3. Let be a graph with vertices and edges.
4. Traverse the graph of Problem 1 by breadth-first search and construct the
corresponding breadth-first search tree. Start the traversal at vertex
and resolve ties by the vertex alphabetical order.
37
7. Explain how one can identify connected components of a graph by using
8. A graph is said to be bipartite if all its vertices can be partitioned into
two disjoint subsets and so that every edge connects a vertex in
with a vertex in . (One can also say that a graph is bipartite if its
vertices can be colored in two colors so that every edge has its vertices
9. Write a program that, for a given graph, outputs
(a) vertices of each connected component.
10. One can model a maze by having a vertex for a starting point, a finishing
point, dead ends, and all the points in the maze where more than one path
can be taken, and then connecting the vertices according to the paths in
the maze.
a. Construct such a graph for the following maze.
38
b. Which traversal– DFS or BFS– would you use if you found your-
self in a maze and why?
11. Three Jugs Siméon Denis Poisson (1781—1840), a famous French mathe-
matician and physicist, is said to have become interested in mathematics
Hints to Exercises 3.5
1. a. Use the definitions of the adjacency matrix and adjacency lists given
2. Compare the efficiency classes of the two versions of DFS for sparse graphs.
3. a. What is the number of such trees equal to?
6. a. What property of a BFS forest indicates a cycle’s presence? (The
answer is similar to the one for a DFS forest.)
b. The answer is “no”. Find two examples supporting this answer.
7. Given the fact that both traversals can reach a new vertex if and only if it
is adjacent to one of the previously visited vertices, which vertices will be
visited by the time either traversal halts (i.e., its stack or queue becomes
empty)?
40
Solutions to Exercises 3.5
1. a. Here are the adjacency matrix and adjacency lists for the graph in
question:
⎡
⎢
0111100
⎤
⎥
→→→→
b. See below: (i) the graph; (ii) the traversal’s stack (the first subscript
number indicates the order in which the vertex was visited, i.e., pushed
2. Thetimeefficiency of DFS is Θ(||2)for the adjacency matrix representa-
tion and Θ(||+||)for the adjacency lists representation, respectively.
3. a. The number of DFS trees is equal to the number of connected compo-
nents of the graph. Hence, it will be the same for all DFS traversals of
the graph.
4. Here is the result of the BFS traversal of the graph of Problem 1:
f b
gc
a
c
b
d e
5. We’ll prove the assertion in question by contradiction. Assume that
a BFS tree of some undirected graph has a cross edge connecting two
vertices and such that []≥[]+2But []=[]and
6. a. A graph has a cycle if and only if its BFS forest has a cross edge.
b. Both traversals, DFS and BFS, can be used for checking a graph’s
acyclicity. For some graphs, a DFS traversal discovers a back edge in its
DFS forest sooner than a BFS traversal discovers a cross edge (see exam-
7. Start a DFS (or BFS) traversal at an arbitrary vertex and mark the visited
vertices with 1. By the time the traversal’s stack (queue) becomes empty,
8. a. Let beaDFSforestofagraph. Itisnotdifficult to see that
is 2-colorable if and only if there is no back edge connecting two vertices
9. n/a
43
11. The sequence shown in the figure below solves the puzzle in six steps,
which is the minimum.
Solution to the Three Jugs puzzle
Although the solution can be obtained by trial and error, there is a system-
atic way of getting to it. We can represent a state of the jars by a triple of
nonnegative integers indicating the amount of water in the 3-pint, 5-pint, and
44
states reachable from it by the triple of the front state, add them to the queue,
and then delete the front state from the queue. After a desired state is reached
for the first time, follow the labels backwards to get the shortest sequence of
transformations that solve the puzzle.
45