4

1. GRAP H THEOR Y I N TH E INFORMATIO N AG E

Everything should be made as simple as possible, but not simpler.

Albert Einstein

We intend t o us e as few new definitions a s possible, a s long as the idea s can b e

adequately addressed .

DEFINITION

1. A grap h G consists of a vertex set V(G) and an edge set E(G),

where each edge is an unordered pair of vertices.

For example , Figur e 5 shows a grap h G — (V(G), E(G)) define d a s follows :

V(G) = {a,6,c,d} ,

E(G) = {{a,6},{a,c},{6,c},{6,d},{c,d}} .

The grap h i n Figure 5 is a simple grap h sinc e i t doe s not contai n loops or multipl e

edges. Figur e 6 is a genera l grap h wit h loop s an d multipl e edges .

FIGURE

5 . A simple grap h G.

FIGURE

6 . A multi-graph wit h a loop .

Figure 7 is a graph consistin g o f several mathematicians includin g the authors .

Each edg e denote s researc h collaboratio n tha t resulte d i n a mathematica l pape r

reviewed b y Mathematical Reviews o f the America n Mathematica l Society .

Here ar e severa l equivalen t way s to describ e tha t a n edg e {ix , v} i s in G:

• {u,v}eE(G).

• u an d v ar e adjacent.

• u i s a neighbor o f v.

• Th e edg e {u , v} i s incident t o u (an d als o to v).