repeated edges is called a cycle with base υ i . If no vertices other than the base
are repeated in a cycle, then it is said to be simple. In Figure 1.1, (υ 1 , υ 3 ), (υ 3 , υ 2 )
is a simple path from υ 1 to υ 2 . The sequence of edges (υ 1 , υ 3 ), (υ 3 , υ 3 ), (υ 3 , υ 1 ) is
a cycle, but not a simple one. If the edges of a graph are labeled, we can talk
about the label of a walk. This label is the sequence of edge labels encountered
when the path is traversed. Finally, an edge from a vertex to itself is called a
loop. In Figure 1.1, there is a loop on vertex υ 3 .
Figure 1.1
On several occasions, we will refer to an algorithm for finding all simple
paths between two given vertices (or all simple cycles based on a vertex). If we
do not concern ourselves with efficiency, we can use the following obvious
method. Starting from the given vertex, say υ i , list all outgoing edges (υ i , υ k ), (υ i ,
υ l ),…At this point, we have all paths of length one starting at υ i . For all vertices
υ k , υ l ,…so reached, we list all outgoing edges as long as they do not lead to any
vertex already used in the path we are constructing. After we do this, we will
have all simple paths of length two originating at υ i . We continue this until all
possibilities are accounted for. Since there are only a finite number of vertices,
we will eventually list all simple paths beginning at υ i . From these we select
those ending at the desired vertex.
Trees are a particular type of graph. A tree is a directed graph that has no
cycles, and that has one distinct vertex, called the root, such that there is exactly
one path from the root to every other vertex. This definition implies that the root
has no incoming edges and that there are some vertices without outgoing edges.
These are called the leaves of the tree. If there is an edge from υ i to υ j , then υ i is
said to be the parent of υ j , and υ j the child of υ i . The level associated with each
vertex is the number of edges in the path from the root to the vertex. The height
of the tree is the largest level number of any vertex. These terms are illustrated in
Figure 1.2.
are repeated in a cycle, then it is said to be simple. In Figure 1.1, (υ 1 , υ 3 ), (υ 3 , υ 2 )
is a simple path from υ 1 to υ 2 . The sequence of edges (υ 1 , υ 3 ), (υ 3 , υ 3 ), (υ 3 , υ 1 ) is
a cycle, but not a simple one. If the edges of a graph are labeled, we can talk
about the label of a walk. This label is the sequence of edge labels encountered
when the path is traversed. Finally, an edge from a vertex to itself is called a
loop. In Figure 1.1, there is a loop on vertex υ 3 .
Figure 1.1
On several occasions, we will refer to an algorithm for finding all simple
paths between two given vertices (or all simple cycles based on a vertex). If we
do not concern ourselves with efficiency, we can use the following obvious
method. Starting from the given vertex, say υ i , list all outgoing edges (υ i , υ k ), (υ i ,
υ l ),…At this point, we have all paths of length one starting at υ i . For all vertices
υ k , υ l ,…so reached, we list all outgoing edges as long as they do not lead to any
vertex already used in the path we are constructing. After we do this, we will
have all simple paths of length two originating at υ i . We continue this until all
possibilities are accounted for. Since there are only a finite number of vertices,
we will eventually list all simple paths beginning at υ i . From these we select
those ending at the desired vertex.
Trees are a particular type of graph. A tree is a directed graph that has no
cycles, and that has one distinct vertex, called the root, such that there is exactly
one path from the root to every other vertex. This definition implies that the root
has no incoming edges and that there are some vertices without outgoing edges.
These are called the leaves of the tree. If there is an edge from υ i to υ j , then υ i is
said to be the parent of υ j , and υ j the child of υ i . The level associated with each
vertex is the number of edges in the path from the root to the vertex. The height
of the tree is the largest level number of any vertex. These terms are illustrated in
Figure 1.2.