Algorithmics - The Computing Universe: A Journey through a Revolution - page 91

Fig. 5.6. An example of the merge sort
algorithm that uses a divide-and-conquer
approach to reduce the list to sets of
pairs of names. These are ordered and
the different pairs merged together in
the correct order.

BT APJ F ME

BTAP J F ME

BT AP JF ME

BT AP FJ EM

T

P
A

M

J

B

E

F

ABPT

EF MJ

M

T

J

P

F

B

A E

M

ABEFJ P T

proved that there was no solution, and in so doing he laid the foundations of
graph theory and the beginnings of the study of topology.
Euler solved the problem by reducing it to essentials. The choice of route
on land is unimportant: only the sequence of bridges crossed is relevant
( Fig. 5.7b ). The map can be further simplified by replacing each landmass
with a dot - called a “vertex” or a “node” - and each bridge by a line - called
an “edge” - joining two vertices ( Fig. 5.7c ). Only the connection information
in the resulting “graph” is important for this problem, not details of the
layout of the figure. This illustrates one of the key ideas of topology: topol-
ogy is not concerned with the rigid shape of objects or surfaces, just their
connectivity.
Euler then observed that, except for the start and finish of the walk, when-
ever one enters a vertex (landmass) by a bridge, one must leave the same land-
mass or vertex by another bridge. If each bridge is crossed only once, except

Fig. 5.7. Three representations of
the Seven Bridges of Königsberg: (a)
Königsberg in Euler's time; (b) a more
abstract representation of the seven
bridges; and (c) a graph of the seven
bridges.

(a) (b) (c)