478
Graphs and Trees
Definition Graph
(formal)
A graph is an ordered triple (N, A, g) where
N = a nonempty set of nodes (vertices)
A = a set of arcs (edges)
g = a function associating with each arc a an unordered pair x–y of nodes
called the endpoints of a
We might want the arcs of a graph to begin at one node and end at another, in
which case we would use a directed graph.
Definition DirecTeD Graph
A directed graph (digraph) is an ordered triple (N, A, g) where
N = a nonempty set of nodes
A = a set of arcs
g = a function associating with each arc a an ordered pair (x, y) of nodes
where x is the initial point and y is the terminal point of a.
In a directed graph, then, there is a direction associated with each arc.
example 3
For the graph of Figure 6.3, the function g associating arcs with endpoints performs
the following mapping: g(a 1 ) = 1–2, g(a 2 ) = 1–2, g(a 3 ) = 2–2, g(a 4 ) = 2–3,
g(a 5 ) = 1–3, and g(a 6 ) = 3–4.
example 4
Figure 6.4 shows a directed graph. There are 4 nodes and 5 arcs. The function g
associating arcs with endpoints performs the mapping g(a 1 ) = (1, 2), meaning that
arc a 1 begins at node 1 and ends at node 2. Also, g(a 3 ) = (1, 3), but g(a 4 ) = (3, 1).
2
1
4
3
a 1
a 2
a 5
a 3
a 4
Figure 6.4
Besides imposing direction on the arcs of a graph, we may want to modify the
basic definition of a graph in other ways. We often want the nodes of a graph to carry identifying information, like the names of the cities in the map of airline routes.
praCTiCe 1 Sketch a graph having nodes 51, 2, 3, 4, 56, arcs 5a 1 , a 2 , a 3 , a 4 , a 5 , a 6 6, and function
g(a 1 ) = 1–2, g(a 2 ) = 1–3, g(a 3 ) = 3–4, g(a 4 ) = 3–4, g(a 5 ) = 4–5, and g(a 6 ) = 5–5. ■
Graphs and Trees
Definition Graph
(formal)
A graph is an ordered triple (N, A, g) where
N = a nonempty set of nodes (vertices)
A = a set of arcs (edges)
g = a function associating with each arc a an unordered pair x–y of nodes
called the endpoints of a
We might want the arcs of a graph to begin at one node and end at another, in
which case we would use a directed graph.
Definition DirecTeD Graph
A directed graph (digraph) is an ordered triple (N, A, g) where
N = a nonempty set of nodes
A = a set of arcs
g = a function associating with each arc a an ordered pair (x, y) of nodes
where x is the initial point and y is the terminal point of a.
In a directed graph, then, there is a direction associated with each arc.
example 3
For the graph of Figure 6.3, the function g associating arcs with endpoints performs
the following mapping: g(a 1 ) = 1–2, g(a 2 ) = 1–2, g(a 3 ) = 2–2, g(a 4 ) = 2–3,
g(a 5 ) = 1–3, and g(a 6 ) = 3–4.
example 4
Figure 6.4 shows a directed graph. There are 4 nodes and 5 arcs. The function g
associating arcs with endpoints performs the mapping g(a 1 ) = (1, 2), meaning that
arc a 1 begins at node 1 and ends at node 2. Also, g(a 3 ) = (1, 3), but g(a 4 ) = (3, 1).
2
1
4
3
a 1
a 2
a 5
a 3
a 4
Figure 6.4
Besides imposing direction on the arcs of a graph, we may want to modify the
basic definition of a graph in other ways. We often want the nodes of a graph to carry identifying information, like the names of the cities in the map of airline routes.
praCTiCe 1 Sketch a graph having nodes 51, 2, 3, 4, 56, arcs 5a 1 , a 2 , a 3 , a 4 , a 5 , a 6 6, and function
g(a 1 ) = 1–2, g(a 2 ) = 1–3, g(a 3 ) = 3–4, g(a 4 ) = 3–4, g(a 5 ) = 4–5, and g(a 6 ) = 5–5. ■