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).
Previous Page Next Page