Discrete Mathematics for Computer Science

The K6nigsberg Bridge Problem 361

A breadth first search could also be used to find the connected components of a graph.

The complexity of such an algorithm would be the same as the algorithm that uses a depth

first search. The design of an algorithm for finding connected components using a breadth

first search is left to the reader.

W The Konigsberg Bridge Problem

In the eighteenth century, the city of Konigsberg, Prussia, had seven bridges that crossed

the Pregel River. The bridges connected the two islands in the river with each other and

with the opposite banks. Figure 6.25 shows the configuration of the bridges.

C

KNEIPHOFF D

A

B

Figure 6.25 K6nigsberg bridges on the Pregel River.

The town's folk had wondered if the following problem, called the Konigsberg Bridge

Problem, had a solution: Is there a continuous walk starting at C that crosses each of the

seven bridges exactly once and returns the walker to C? The problem was initially solved

by the famous mathematician Leonhard Euler (1707-1783, b. Switzerland), who modeled

the problem with a graph and then found necessary and sufficient conditions for the graph

constructed to represent a walk of the required kind.

To define a graph that represents the problem, let each piece of land be a vertex. Each

bridge defines an edge joining the vertices that represent the pieces of land at the ends of the

bridge. For the Konigsberg Bridge Problem, the resulting graph is shown in Figure 6.26.

C

A >D

B

Figure 6.26 K6nigsberg bridge graph.

Properly speaking, the model in Figure 6.26 is not a graph, because there are pairs

of vertices with more than a single edge joining them. This extension of the notion of a

graph is called a multigraph. The extension of Euler's theorem to multigraphs would not