Java Reference
In-Depth Information
Many real-world problems can be solved using graph algorithms.
Key
Point
Graphs are useful in modeling and solving real-world problems. For example, the problem
to find the least number of flights between two cities can be modeled using a graph, where
the vertices represent cities and the edges represent the flights between two adjacent cities,
as shown in Figure 28.1. The problem of finding the minimal number of connecting flights
between two cities is reduced to finding a shortest path between two vertices in a graph.
problem
Seattle (0)
Boston (6)
Chicago (5)
New York (7)
Denver (3)
San Francisco (1)
Kansas City (4)
Los Angeles (2)
Atlanta (8)
Dallas (10)
Houston (11)
Miami (9)
F
IGURE
28.1
A graph can be used to model the flights between the cities.
The study of graph problems is known as
graph theory
. Graph theory was founded by
Leonhard Euler in 1736, when he introduced graph terminology to solve the famous
Seven
Bridges of Königsberg
problem. The city of Königsberg, Prussia (now Kaliningrad, Russia),
was divided by the Pregel River. There were two islands on the river. The city and islands
were connected by seven bridges, as shown in Figure 28.2a. The question is, can one take a
walk, cross each bridge exactly once, and return to the starting point? Euler proved that it is
not possible.
graph theory
Seven Bridges of Königsberg
A
A
C
D
Island 1
Island 2
C
D
B
B
(a) Seven bridges sketch
(b) Graph model
F
IGURE
28.2
Seven bridges connected islands and land.
To establish a proof, Euler first abstracted the Königsberg city map by eliminating all
streets, producing the sketch shown in Figure 28.2a. Next, he replaced each land mass with
Search WWH ::
Custom Search