A digraph G

is said to be monopathic if for every pair of its distinct vertices u

and v

there is at most one simple path directed from u

to v

(and at most one from v

to u

).

Now let G

be an arbitrary strongly connected digraph. How many of the following five statements are true?

G

is monopathic if and only if GT

is monopathic.

G

is monopathic if and only if both DFS(G)

and DFS(GT)

have no forward-edges and no cross-edges.

G

is monopathic if and only if any pair of distinct simple cycles in G

have at most one vertex in common.

G

is monopathic if and only if removal of any single non-self-loop edge from G

will make it not strongly connected.

G

is monopathic if and only if DFS(G)

has no forward-edges and no cross-edges, and for each vertex u

other than the DFS-root, there is a unique back-edge (x,y)

such that x

is a descendant of u

and y

is a proper ancestor of u

(with respect to the DFS-tree).

Question 19Answer

a.

0.

b.

2.

c.

4.

d.

5.

e.

1.

f.

3.