For the digraph in Figure 1: Find a subgraph which is not a generated subgraph.
ID: 3772117 • Letter: F
Question
For the digraph in Figure 1: Find a subgraph which is not a generated subgraph. Find a subgraph generated by vertices 5, 8. and 9. Find a strongly connected generated subgraph which is not a strong component. Find all strong components. You may define these in terms of their generating vertex set, e.g. K_1, = {12.13.14}. Find its condensation. Find a vertex basis. Determine the number of vertex bases. A set C of vertices in a digraph D is called a vertex if every vertex can reach some vertex of C and C is minimal in the sense that no proper subset of C has this property. Find all vertex contra bases of the digraph in Figure 1. For the digraph in Figure 1. identify all strong components using matrices. Suppose A is a matrix of Os mid Is. with Is down the diagonal (and perhaps elsewhere). Is R necessarily the reachability matrix of some digraph? (Give a proof or counterexample).Explanation / Answer
1.
a) Subgraph:
b)
Subgraph generated by vertices 5,8,9:
f)Vertex base in this graph is an empty set.
g)The number of vertices of vertex base is 0.