Problems in Graph
Problems
·
Königsberg Bridge Problem:
o
The Königsberg bridge problem is perhaps the
best-known example in graph theory.
o
It was a long-standing problem until solved by
Leonhard Euler (1707-1783) in 1736, by means of a graph.
o
Euler wrote the first paper ever in graph theory
and thus became the originator of the theory of graphs as well as of the rest
of topology.
o
The problem is depicted in figure below.
§
o
The problem was to start at any of the four land
areas of the city, A, B, C, or D, walk over each of the seven bridges exactly
once, and return to the starting point.
·
Utilities Problem:
o
There are three houses H1 , H2 , and H3 , each
to be connected to each of the three utilities—water (W), gas (G), and
electricity (E)— by means of conduits.
