Discrete math Given the following directed graph which of th

Discrete math

Given the following directed graph which of the following are valid paths? a. a. a. a. c, a. a e. c, d, b, a, b, c, d b, c, d, e, a, a, a, a, b a, a, b, c, d, e, a

Solution

1. a, a, a, a, c, a, a: a recursively can be visited a, but there is no path from a to c. Therefore, this is not a valid path.

2. e, c, d, b, a, b, c, d: There is a path from e to c, c to d, but there is no path from d to b. Therefore, this is not valid.

3.. b, c, d, e, a, a, a, a, b: There is a path from b to c, c to d, d to e, e to a, a to a recursively, and from a to b. Therefore, this is a valid path.

4. a, a, b, c, d, e, a: There is a recursive path from a to a, and there are paths from a to b, b to c, c to d, d to e, and e to a. Therefore, this is also a valid path.

Therefore, the answers are 3, 4.