1.
How many constraints does flow have?
A
One
B
Three
C
Two
D
Four
View Answer
Correct Answer: C — Two
Explanation:
A flow is a mapping which follows two constraints — conservation of flows and capacity constraints.
Loading practice questions
14 practice sets · Page 1 of 1
How many constraints does flow have?
One
Three
Two
Four
Correct Answer: C — Two
Explanation:
A flow is a mapping which follows two constraints — conservation of flows and capacity constraints.
What is the running time of Dinic's blocking flow algorithm?
O(V^2E)
O(VE^2)
O(V^3)
O(E max |f|)
Correct Answer: A — O(V^2E)
Explanation:
The running time of Dinic's blocking flow algorithm is O(V²E). The running time of Ford-Fulkerson algorithm is O(E max |f|).
Who formulated the Maximum flow problem?
Lester R. Ford and Delbert R. Fulkerson
T.E. Harris and F.S. Ross
Y.A. Dinitz
Kruskal
Correct Answer: B — T.E. Harris and F.S. Ross
Explanation:
The first people to formulate the Maximum flow problem were T.E. Harris and F.S. Ross.
What is the running time of an unweighted shortest path algorithm whose augmenting path is the path with the least number of edges?
O(E)
O(EV)
O(EV^2)
O(E log V)
Correct Answer: C — O(EV^2)
Explanation:
Each augmenting step takes O(|E|) using an unweighted shortest path algorithm, yielding an O(|E|²|V|) bound on the running time.
Dinic's algorithm runs faster than the Ford-Fulkerson algorithm.
True
False
Correct Answer: A — True
Explanation:
True. Dinic's algorithm includes construction of level graphs and residual graphs and finding of augmenting paths along with blocking flow, and is faster than the Ford-Fulkerson algorithm.
In what time can an augmenting path be found?
O(|E| log |V|)
O(|E|)
O(|E|·|V|^2)
O(|E|·|V|^2 log |V|)
Correct Answer: B — O(|E|)
Explanation:
An augmenting path can be found in O(|E|) time by an unweighted shortest path algorithm.
A simple acyclic path between source and sink which passes through only positive weighted edges is called?
Augmenting path
Critical path
Residual path
Maximum path
Correct Answer: A — Augmenting path
Explanation:
An augmenting path between source and sink is a simple path without cycles. A path consisting of zero slack edges is called a critical path.
Under what condition can a vertex combine and distribute flow in any manner?
It may violate edge capacities
It should maintain flow conservation
The vertex should be a source vertex
The vertex should be a sink vertex
Correct Answer: B — It should maintain flow conservation
Explanation:
A vertex can combine and distribute flow in any manner but it should not violate edge capacities and it should maintain flow conservation.
The first step in the naive greedy algorithm is?
Analysing the zero flow
Calculating the maximum flow using trial and error
Adding flows with higher values
Reversing flow if required
Correct Answer: A — Analysing the zero flow
Explanation:
The first step in the naive greedy algorithm is to start with the zero flow, followed by adding edges with higher values.
Does Ford-Fulkerson algorithm use the idea of?
Naive greedy algorithm approach
Residual graphs
Minimum cut
Minimum spanning tree
Correct Answer: B — Residual graphs
Explanation:
Ford-Fulkerson algorithm uses the idea of residual graphs, which is an extension of the naive greedy approach allowing undo operations.
Which algorithm is used to solve a maximum flow problem?
Prim's algorithm
Kruskal's algorithm
Dijkstra's algorithm
Ford-Fulkerson algorithm
Correct Answer: D — Ford-Fulkerson algorithm
Explanation:
The Ford-Fulkerson algorithm is used to compute the maximum feasible flow between a source and a sink in a network.
What is the source?
Vertex with no incoming edges
Vertex with no leaving edges
Centre vertex
Vertex with the least weight
Correct Answer: A — Vertex with no incoming edges
Explanation:
A vertex with no incoming edges is called a source. A vertex with no leaving edges is called a sink.
A network can have only one source and one sink.
False
True
Correct Answer: B — True
Explanation:
True. A network can have only one source and one sink in order to find the feasible flow in a weighted connected graph.
What does Maximum flow problem involve?
Finding a flow between source and sink that is maximum
Finding a flow between source and sink that is minimum
Finding the shortest path between source and sink
Computing a minimum spanning tree
Correct Answer: A — Finding a flow between source and sink that is maximum
Explanation:
The maximum flow problem involves finding a feasible flow between a source and a sink in a network that is maximum, not minimum.