SECTION 2.2 Elementary Graph Theory 111
would ideally choose a route that would allow him to avoid walking
the same street twice. Thus, if the town is represented by a simple
graph whose edges represent the streets, then the problem is clearly
that of finding a trail in the graph which includes every edge: such a
trail is called anEulerian trail. If the postman is to begin and end at
the same vertex, then what is sought is anEulerian circuit. General
problems such as this are calledrouting problems.
Classic Example. In the ancient
city of K ̈onigsberg (Germany) there
were seven bridges, arranged in a
“network” as depicted in the figure
below:
A prize was offered to anyone who could determine a route by which
each of the bridges can be traversed once and then return to the starting
point.
A casual inspection of the above lay-
out of bridges shows that this can be rep-
resented by a graph having four vertices
and seven edges, as in the graph to the
right.
From the above, we see that the ad-
jacency matrix for the seven bridges of
K ̈onigsberg with labeling A = 1, B =
2 , C= 3,andD= 4 is given by
A =
0 2 2 1
2 0 0 1
2 0 1 0
1 1 1 0