Post by vsiap on Nov 27, 2014 23:14:31 GMT
Definition. A vertex basis of a directed graph (digraph) G is a subset of V such that for each u in V, there is a path to u from some v in B, and the set B is minimal.
In the directed graph in Exercise 5, there is a path from b to each of the other three vertices, so {b} is a vertex basis (and a smallest one). It is easy to see that {c} and {d} are also vertex bases, but a is not in any vertex basis. For the directed graph in Exercise 6, there is a path from b to each of a and c; on the other hand, d must clearly be in every vertex basis. Thus {b,d} is a smallest vertex basis. So are {a,d} and {c,d}.
In the directed graph in Exercise 5, there is a path from b to each of the other three vertices, so {b} is a vertex basis (and a smallest one). It is easy to see that {c} and {d} are also vertex bases, but a is not in any vertex basis. For the directed graph in Exercise 6, there is a path from b to each of a and c; on the other hand, d must clearly be in every vertex basis. Thus {b,d} is a smallest vertex basis. So are {a,d} and {c,d}.