Discrete Mathematical Structures by Pearson

2-18 Discrete Mathematical Structures

Obviously, a path of length n involves n + 1 elements of A that may not be necessarily distinct.

A diagraph of a relation can be used to identify a path. The succession of edges in a diagraph

where the indicated direction is followed provides the path, whose length is the number of edges

and where all the vertices need not be distinct.

Cycle: A path that begins and ends at the same vertex is called a cycle. Consider the following

diagraph.

1

2

3

4

5

6

Then

p

1

: 1, 2, 3, 4, 5 is a path of length 4.

p

2

: 1, 2, 5, 6, 1 is a path of length 4. It is a cycle.

p

3

: 3, 3 is a cycle of length 1.

p

4

: 2, 5, 6, 1, 2 is a cycle of length ...