relationship defined. He did not require that the line
representing Bbe at right angles to the reference line.
French mathematician and philosopher R
ENÉ
D
ESCARTES
(1596–1650) independently developed the
same technique, but he had the further insight to intro-
duce algebraic symbolism to describe relationships via
formulae and to label graphs appropriately. Descartes
too, however, envisioned functions as sliding lengths
along a single reference line. It was not until decades
later that mathematicians began drawing an explicit
second coordinate axis, the y-axis, at a fixed 90°angle
to the horizontal reference x-axis.
Quantities other than functions can also be
graphed. For example, an inequality of the form y< x
+ 3 defines the
HALF
-
PLANE
below the line y= x+ 3.
The graph of a function of two variables z= f(x, y) is a
surface sitting in three-dimensional space. For example,
the graph of the function z= x2+ y2is a
PARABOLOID
.
A logarithmic graph is one in which both axes of
the coordinate system are marked in
LOGARITHMIC
SCALE
. Such plots are particularly useful for examining
equations of the form y= axn. A polar-coordinate
graph is a plot of an equation of the form r= f(θ) given
in
POLAR COORDINATES
. Polar-coordinate graph paper
assists in plotting such graphs.
Graphs of other types of numerical relationships
are studied in descriptive statistics.
See also
CONCAVE UP
/
CONCAVE DOWN
;
COORDI
-
NATES
;
GRAPHICAL SOLUTION
;
HISTORY OF FUNCTIONS
(essay);
INCREASING
/
DECREASING
;
MAXIMUM
/
MINIMUM
;
STATISTICS
:
DESCRIPTIVE
.
graph theory The mathematical study of graphs is
called graph theory. The field was founded in 1736 by
the Swiss mathematician L
EONHARD
E
ULER
(1707–83)
with his solution to the famous seven bridges of
Königsberg problem:
The old German city of Königsberg (now the
Russian city of Kaliningrad) was built on the
two banks of the river Pregel and on two
islands in the river. The different parts of the
city were connected by seven bridges. A debate
ensued among the residents as to whether it
was possible to walk a complete tour of the
city crossing each and every bridge precisely
once. (It wasn’t deemed necessary to return to
one’s starting location.) Most people felt that
this was impossible, but could this be proved
to be the case?
Euler’s insight into solving the problem came by
reducing the city plan to a
GRAPH
, that is, a diagram of
points (vertices) and edges, with each point represent-
ing a land mass, and each edge a bridge. Any stroll
through the city thus corresponds to a journey along
the edges of the graph. The Königsberg bridge problem
is therefore equivalent to asking:
Is it possible to draw the above graph without
lifting pencil from page and without tracing
over the same edge twice?
Euler was able to solve the more general problem
of classifying all those graphs that can be so traced. He
observed that, in tracing such a path, any edge drawn
entering a vertex must be matched by an edge exiting
that vertex. Thus all the edges meeting at each vertex
are matched in pairs unless one starts or ends a jour-
ney at a particular vertex, in which case one edge
remains unmatched. Thus a graph that can be so
traced must contain just two vertices of odd degree—
these will be the start and end of the journey; or no
vertices of odd degree—the path starts and ends at the
same location. Any graph containing more than two
vertices of odd degree cannot be drawn without lifting
pencil from page. In particular, the seven bridges of
Königsberg problem cannot be solved (all four vertices
have odd degree).
Any path that traces through a graph following
each edge precisely once is known today as an Eulerian
path. If the path starts and ends at the same vertex it is
called an Eulerian circuit. Euler went further to show
that all connected graphs possessing precisely two ver-
tices of odd degree do indeed have Eulerian paths, and
that graphs with all vertices of even degree do possess
graph theory 235
The seven bridges of Königsberg problem