Advanced High-School Mathematics

SECTION 2.2 Elementary Graph Theory 109

(Just do the long multiplication showing that

(1−x−x^2 )

Ñ∞

∑

k=1

Fkxk

é

=x. This says that the rational function

x

1 −x−x^2

is agenerating functionfor the Fibonacci sequence.)

20. A sequence a 1 , a 2 , a 3 , ..., of real numbers is called a harmonic
    sequence if for each n ≥ 1 , an+1 is the harmonic mean of an
    andan+2(see Exercise 9 of page 42). Show that a given sequence
    a 1 , a 2 , ...is a harmonic sequence if and only if allai 6 = 0 and the
    sequence of reciprocals

1

a 1

,

1

a 2

,

1

a 3

is an arithmetic sequence.

2.2 Elementary Graph Theory

In this section we shall consider one of the most important topics in
contemporary discrete mathematics—that of agraph. This concept
has a huge variety of applications and has become especially important
to the relatively new discipline ofmanagement science.

Mathematically, a graph is easy enough to define. It consists of a set
V of verticesand a numerical relationship between pairs of vertices
(sort of a “distance” or “cost” function). Namely, between any two
vertices vi and vj is a non-negative real number cij such that it is
always true that cij = cji. If cij 6 = 0 we call{vi,vj} an edge. Put
intuitively, the cost of getting from vertexvi to vj is the same as the
cost of getting from vertexvjtovi. In other words, the matrixC= [cij]
is asymmetric matrix, called theadjacency matrix.^28 This matrix is
called theadjacency matrix of the graph.

If the costscijsatisfycii= 0 for all indicesi, andcij is always 0 or
1, then we call the graph asimple graph; otherwise we call the graph
aweighted graph. Perhaps the pictures below will clarify this.

(^28) If this matrix isn’t symmetric, then the graph is called adirected graph; we’ll study those
briefly in Subsection 2.2.3.