数学专业英语(Doc版).25
-
数学专业英语－
The Theory of
Graphs
In
this
chapter,
we
shall
introduce
the
concept
of
a
graph
and
show
that
graph
s
can
be
defined
by
square
matrices
and
versa.
1.
Introduction
Graph
theory
is
a
rapidly
growing
branch
of
mathematics.
The
graphs
discusse
d
in
this
chapter
are
not
the
same
as
the
graphs
of
functions
that
we
studied
previously,
but
a
totally
different
kind.
Like
many
of
the
important
discoveries
and
new
areas
of
learning,
graph
the
ory
also
grew
out
of
an
interesting
physical
problem,
the
so-called
Konigsberg
bridge
problem.
(this
problem
is
discussed
in
Section
2)
The
outstanding
Swis
s
mathematician,
Leonhard
Euler
(1707-1783)
solved
the
problem
in
1736,
thus
laying
the
foundation
for
this
branch
of
mathematics.
Accordingly,
Euler
is
ca
lled
the
father
of
graph
theory.
Gustay
Robert
Kirchoff
(1824-1887),
a
German
physicist,
applied
graph
theor
y
in
his
study
of
electrical
networks.
In1847,
he
used
graphs
to
solve
systems
of
linear
equations
arising
from
electrical
networks,
thus
developing
an
importa
nt
class
of
graphs
called
trees.
In
1857,
Arthur
Caylcy
discovered
trees
while
working
on
differential
equati
ons.
Later,
he
used
graphs
in
his
study
of
isomers
of
saturated
hydrocarbons.
Camille
Jordan
(1838-1922),
a
French
mathematician,
William
Rowan
Hamilt
on,
and
Oystein
Ore
and
Frank
Harary,
two
American
mathematicians,
are
also
known
for
their
outstanding
contributions
to
graph
theory.
Graph
theory
has
important
applications
in
chemistry,
genetics,
management
s
cience,
Markov
chains,
physics,
psychology,
and
sociology.
Throughout
this
chapter,
you
will
find
a
very
close
relationship
between
gra
phs
and
matrices.
2.
The
Konigsberg
Bridge
Problem
The
Russian
city
of
Konigsberg
(now
Kaliningrad,
Russia)
lies
on
the
Pregel
River.(See
Fig.1)
It
consists
of
banks
A
and
D
of
the
river
and
the
two
island
s
B
and
C.
There
are
seven
bridges
linking
the
four
parts
of
the
city.
Residents
of
the
city
used
to
take
evening
walks
from
one
section
of
the
cit
y
to
another
and
go
over
some
of
these
bridges.
This,
naturally,
suggested
the
following
interesting
problem:
can
one
walk
through
the
city
crossing
each
bri
dge
exactly
once?
The
problem
sounds
simple,
doesn
’
t
it?You
might
want
to
try
a
few
paths
before
going
any
further.
After
all,
by
the
fundamental
countin
g
principle,
the
number
of
possible
paths
cannot
exceed
7!=5040.
Nonetheless,
it
would
be
time
consuming
to
look
at
each
of
them
to
find
one
that
works.
Fig
.1
The
city
of
Konigsberg
In
1736,
Euler
proved
that
no
such
walk
is
possible.
In
fact,
he
proved
a
far
more
general
theorem,
of
which
the
Konigsberg
bridge
problem
is
a
special
ca
se.
Fig
.2
A
mathematical
model
for
the
Konigsberg
bridge
problem
Let
us
construct
a
mathematical
model
for
this
e
each
area
of
the
city
by
a
point
in
a
plane.
The
points
A,
B,
C,and
D
denote
the
areas
th
ey
represent
and
are
called
vertices.
The
arcs
or
lines
joining
these
points
repr
esent
the
represent
the
respective
bridges.
(See
图２
)They
are
called
edges.
The
Konigsberg
bridge
problem
can
now
be
stated
as
follows:
Is
it
possible
to
tra
ce
this
figure
without
lifting
your
pencil
from
paper
or
going
over
the
same
e
dge
twice?
Euler
proved
that
a
figure
like
this
can
be
traced
without
lifting
pe
ncil
and
without
traversing
the
same
edge
twice
if
and
only
if
it
has
no
more
than
weo
vertices
with
an
odd
number
of
edges
joining
them.
Observe
that
m
ore
than
two
vertices
in
the
figure
have
an
odd
number
of
edges
connecting
t
hem
-----in
fact,they
all
do.
1.
Graphs
Let
us
return
to
the
example
Friendly
Airlines
flies
to
the
five
cities,
Boston
(B),
Chicago
(C),
Detroit
(D),
Eden
(E),
and
Fairyland
(F)
as
follows:
it
has
direct
daily
flights
from
city
B
to
cities
C,
D,
and
F,
from
C
to
B,
D,
and
E;
from
D
to
B,
C,
and
F,
from
E
to
C,
and
from
F
to
B
and
D.
This
informat
ion,
though
it
sounds
complicated,
can
be
conveniently
represented
geometrically,
as
in
图
3.
Each
city
is
represented
by
a
heavy
dot
in
the
figure;
an
arc
or
a
line
segment
between
two
dots
indicates
that
ther
e
is
a
direct
flight
between
these
cities.
What
does
this
figure
have
in
common
with
图２
?
Both
consist
of
points
(denoted
by
thick
dots
)
co
nnected
by
arcs
or
line
segments.
Such
a
figure
is
called
a
graph.
The
points
are
the
vertices
of
the
gra
ph;
the
arcs
and
line
segments
are
its
edges.
More
generally,
we
make
the
following
definition:
A
graph
consists
of
a
finite
set
of
points,
together
with
arcs
or
line
segments
connecting
some
of
them.
These
points
are
called
the
vertices
of
the
graph;
the
arcs
and
line
segments
are
called
the
edges
og
the
graph.
The
vertices
of
graph
are
usually
denoted
by
the
letters
A,
B,
C,
and
so
on.
An
edge
joining
th
e
vertices
A
and
B
is
denoted
by
AB
or
A-B.
Fig
.3
图２
and
图
3
are
graphs.
Other
graphs
are
shown
in
图
4.
The
graph
in
图２
has
four
vertices
A,
B,
C,
and
D,
and
seven
edges
AB,
AB,
AC,
BC,
BD,
CD,
and
BD.
For
the
graph
in
图
4b,
there
are
four
vertices,
A,
B,
C,
and
D,
but
only
two
edges
AD
and
CD.
Consider
the
graph
in
图
4c,
it
contains
an
ed
ge
emanating
from
and
terminating
at
the
same
vertex
A.
Such
an
edge
is
called
a
loop.
The
graph
in
图
4d
contains
two
edges
between
the
vertices
A
and
C
and
a
loop
at
the
vertex
C.
The
number
of
edges
meeting
at
a
vertex
A
is
called
the
valence
or
degree
of
the
vertex,
denoted
by
v
(A). For
the
graph
in
图
4b,
we
have
v(A)=1,
v(B)=0,
v(C)=1,
and
v(D)=2.
In
图
4b,
we
have
v(A)=3,
v(B)
=2,
and
v(C)=4.
A
graph
can
conveniently
be
described
by
using
a
square
matrix
in
which
the
entry
that
belong
to
the
row
headed
by
X
and
the
column
by
Y
gives
the
number
of
edges
from
vertex
X
to
vertex
Y.
This
m
atrix
is
called
the
matrix
representation
of
the
graph;
it
is
usually
denoted
by
the
letter
M.
The
matrix
representation
of
the
graph
for
the
Konigsberg
problem
is
Clearly
the
sum
of
the
entries
in
each
row
gives
the
valence
of
the
corresponding
vertex.
We
have
v(A)
=3,
v(B)=5,
v(C)=3,
as
we
would
expect.
Conversely,
every
symmetric
square
matrix
with
nonnegative
integral
entries
can
be
considered
the
ma
trix
representation
of
some
graph.
For
example,
consider
the
matrix
A B C
D
Clearly,
this
is
the
matrix
representation
of
the
graph
in
图
5.
Vocabulary
Network
网络
Electrical
network
电网络