 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2013/functional-programming-design-and-analysis-of-algorithms/5/a/solution

A length-zero graph path starts and ends at the same vertex. Therefore

P_{0}

is the Boolean identity matrix. A graph path of length at most one is either such a stationary graph path or one original directed edge:

P_{0} [i, j] = (i = j), P_{1} [i, j] = (i = j) \lor E [i, j], P_{1} = I \lor E .

The logical disjunction is entrywise. Diagonal entries of

E

may be false if there are no self-loops, but every diagonal entry of

P_{1}

is true because the zero-length graph path is allowed.

 New to topics? Read the docs here!