Section 6.1 Graphs and Their Representations
481
Graph Terminology
Before proceeding, we need some terminology about graphs. Surprisingly, although there is a large body of literature in graph theory, the terminology is not
completely standard. Therefore other books may give slightly different variations
of some of these terms.
Two nodes in a graph are adjacent if they are the endpoints associated with an
arc. For example in the graph of Figure 6.3 (reproduced here), 1 and 3 are adjacent
nodes but 1 and 4 are not. Node 2 is adjacent to itself. A loop in a graph is an arc
with endpoints n–n for some node n; in Figure 6.3, arc a 3 is a loop with endpoints
2–2. A graph with no loops is loop-free. Two arcs with the same endpoints are
parallel arcs; arcs a 1 , and a 2 in Figure 6.3 are parallel. A simple graph is one
with no loops or parallel arcs. An isolated node is adjacent to no other node; in
Figure 6.3, 5 is an isolated node. The degree of a node is the number of arc ends
at that node. In Figure 6.3, nodes 1 and 3 have degree 3, node 2 has degree 5, node
4 has degree 1, and node 5 has degree 0.
1
3
4
5
a 1
2
a 2
a 3
a 4
a 5
a 6
Because the function g that relates arcs to endpoints in the formal definition of
a graph is indeed a function, each arc has a unique pair of endpoints. If g is a one-toone function, then there is at most one arc associated with a pair of endpoints; such
Input units
Hidden layer
Output units
w 1
1, 1
w 1
1, 2
w 1
2, 1
w 1
1, j
w 1
2, j
w 1
i, 1
w 1
i, 2
w 1
i, j
w 2
j, k
w 2
j, 1
w 2
2, k
w 2
2, 1
w 2
1, k
w 2
1, 1
w 1
2, 2
Figure 6.9