|
Figure 5-4. A dodecahedron, where the objective is to trace the edges so you visit each vertex exactly once. The
illustration is taken from Récréations Mathématiques, vol 2 (Lucas, 1896, p. 205)
Chapter 5
■
traversal: the skeleton key of algorithmiCs
99
it’s not so hard to see that connectedness and even-degree nodes are necessary conditions (disconnectedness
is clearly a barrier, and an odd-degree node will necessarily stop your tour at some point). it’s a little less obvious
that they are sufficient conditions. We can prove this by induction (big surprise, eh?), but we need to be a bit
careful about our induction parameter. if we start removing nodes or edges, the reduced problem may no longer
be eulerian, and our induction hypothesis won’t apply. let’s not worry about connectivity. if the reduced graph
isn’t connected, we can apply the hypothesis to each connected component. But what about the even degrees?
We’re allowed to visit the nodes as often as we want, so what we’ll be removing (or “using up”) is a set of edges.
if we remove an even number of edges from each node we visit, out hypothesis will apply. one way of doing this
would be to remove the edges of some closed walk (not necessarily visiting all nodes, of course). the question
is whether such a closed walk will always exist in an eulerian graph. if we just start walking from some node, u,
every node we enter will go from even degree to odd degree, so we can safely leave it again. as long as we never
visit an edge twice, we will eventually get back to u.
now, let the induction hypothesis be that any connected graph with even-degree nodes and fewer than E edges
has a closed walk containing each edge exactly once. We start with E edges and remove the edges of an arbitrary
closed walk. We now have one or more eulerian components, each of which is covered by our hypothesis. the
last step is to combine the euler tours in these components. our original graph was connected, so the closed walk
we removed will necessarily connect the components. the final solution consists of this combined walk, with a
“detour” for the euler tour of each component.
in other words, deciding whether a graph is eulerian is pretty easy, and finding an euler tour isn’t that hard either
(see exercise 5-2). the eulerian tour does, however, have a more problematic relative: the hamilton cycle.
the hamilton cycle is named after sir William rowan hamilton, an irish mathematician (among other things),
who proposed it as a game (called The Icosian Game), where the objective is to visit each of the vertices of a
dodecahedron (a 12-sided platonic solid, or d12) exactly once and return to your origin (see figure
5-4
). more
generally, a hamilton cycle is a subgraph containing all the nodes of the full graph (exactly once, as it is a proper
cycle). as i’m sure you can see, königsberg is hamiltonian (that is, it has a hamilton cycle). showing that the
dodecahedron is hamiltonian is a bit harder. in fact, the problem of finding hamilton paths in general graphs
is a hard problem—one for which no efficient algorithm is known (more on this in Chapter 11). sort of odd,
considering how similar the problems are, don’t you think?
A Walk in the Park
It’s late autumn in 1887, and a French telegraphic engineer is wandering through a well-kept garden maze, watching
the leaves beginning to turn. As he walks through the passages and intersections of the maze, he recognizes some
of the greenery and realizes that he has been moving in a circle. Being an inventive sort, he starts to ponder how he
could have avoided this blunder and how he might best find his way out. He remembers being told, as a child, that
if he kept turning left at every intersection, he would eventually find his way out, but he can easily see that such a
simple strategy won’t work. If his left turns take him back where he started before he gets to the exit, he’s trapped in
an infinite cycle. No, he’ll need to find another way. As he finally fumbles his way out of the maze, he has a flash of
insight. He rushes home to his notebooks, ready to start sketching out his solution.
OK, this might not be how it actually happened. I admit it, I made it all up, even the year.
5
What is true, though, is
that a French telegraphic engineer named Trémaux in the late 1880s invented an algorithm for traversing mazes. I’ll
get to that in a second, but first let’s explore the “keep turning left” strategy (also known as the left-hand rule) and see
how it works—and when it doesn’t.
5
Hey, even the story of Newton and the apple is apocryphal.
Chapter 5
■
traversal: the skeleton key of algorithmiCs
100
No Cycles Allowed
Consider the maze in Figure
5-5
. As you can see, there are no cycles in it; its underlying structure is that of a tree,
as illustrated by the figure on the right. Here the “keep one hand on the wall” strategy will work nicely.
6
One way of
seeing why it works is to observe that the maze really has only one inner wall (or, to put it another way, if you put
wallpaper inside it, you could use one continuous strip). Look at the outer square. As long as you’re not allowed
to create cycles, any obstacles you draw have to be connected to it in exactly one place, and this doesn’t create any
problems for the left-hand rule. Following this traversal strategy, you’ll discover all nodes and walk every passage
twice (once in either direction).
a
b
c
d
e
f
g
h
i
j
k
l
Do'stlaringiz bilan baham: |
