Question

Which of the following is not a topological ordering for the graph: A ) O f, e, d, a, c, b O f, a, b, d, e, c O e, f, a, d, c, b O f,a,c,e,d,b QUESTION 4 Which of the following is not part of the definition of a flow? The flow out of the source is 0. O The flow into a vertex (not the source or drain) equals the flow out of that vertex. O The flow on an edge is between 0 and the capacity of the edge (inclusive.) O The flow out of the drain is o.

Answer 1

Topological ordering for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Now if u look at the second option given in the ordering:

f , a , b , d , e , c.

This shows that b is before e but since there is a directed edge from e to b e should come before b , therefore this option is false.

For the 4th question , definition of a flow is given as :

A flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, unless it is a source, which has only outgoing flow, or sink, which has only incoming flow.

Therefore source has only outgoing flow which means flow out of source > 0. So first option is not part of definition of flow.