Reachability relation set

1.7k Views Asked by At

How can i define reachable relation set of R for a given di-graph below?enter image description here

1

There are 1 best solutions below

0
On BEST ANSWER

The reachability relation $R$ for that digraph is the set of all ordered pairs of vertices $\langle x,y\rangle$ such that there is a directed path from $x$ to $y$ in the graph. For example, $\langle b,d\rangle\in R$ by virtue of the path $b\to f\to d$, and $\langle c,c\rangle\in R$ by virtue of the path $c\to d\to c$.

Start with vertex $a$; what vertices can you reach via directed paths from $a$? Then go on to vertices $b,c,d,e$, and $f$ in turn and answer the same question.

There are other ways to find $R$ — using the adjacency matrix of the digraph, for instance — but this is the most basic.