Introduction to Network Flow Algorithms
Explore the basics of network flow algorithms and their applications in backend engineering.
Questions in this quiz
15 questions on Introduction to Network Flow Algorithms. Work through them here, then start the quiz to answer them and see your score.
1.What is the primary goal of the Ford-Fulkerson method?
- ATo detect cycles in a graph
- BTo find the minimum spanning tree
- CTo find the shortest path in a graph
- DTo find the maximum flow in a flow network
2.In a flow network, what does the term 'capacity' refer to?
- AThe maximum flow allowed through an edge
- BThe number of nodes
- CThe total number of edges
- DThe minimum cut of the network
3.Which algorithm is commonly used to find the maximum flow in a network?
- AEdmonds-Karp algorithm
- BBellman-Ford algorithm
- CKruskal's algorithm
- DDijkstra's algorithm
4.What is an 'augmenting path' in the context of network flow?
- AA path that forms a cycle
- BA path that decreases the flow
- CA path that can increase the overall flow
- DA path with no flow
5.What is the 'cut' in a flow network?
- AA single edge with maximum capacity
- BA set of edges that forms a cycle
- CA partition of the vertices into two disjoint subsets
- DA path with minimum flow
6.Which theorem relates maximum flow and minimum cut in a flow network?
- AMax-Flow Min-Cut Theorem
- BFlow Conservation Theorem
- CShortest Path Theorem
- DGraph Partition Theorem
7.What is the time complexity of the Edmonds-Karp algorithm?
- AO(VE^2)
- BO(V^2)
- CO(E log V)
- DO(V + E)
8.In network flow, what does 'flow conservation' mean?
- AThe amount of flow into a node equals the flow out of it
- BFlow is conserved at the source
- CFlow is conserved at every edge
- DFlow is conserved at the sink
9.Which of the following is NOT an application of network flow algorithms?
- AFinding shortest paths
- BTraffic routing
- CImage segmentation
- DBipartite matching
10.What is the main difference between the Ford-Fulkerson and Edmonds-Karp algorithms?
- AThey solve different problems
- BFord-Fulkerson is faster
- CFord-Fulkerson uses DFS, Edmonds-Karp uses BFS
- DEdmonds-Karp uses DFS, Ford-Fulkerson uses BFS
11.What is a 'residual network' in the context of flow networks?
- AA network with minimum cut
- BA network representing remaining capacities
- CA network with maximum flow
- DA network with no flow
12.Which problem can be solved using the Max-Flow Min-Cut Theorem?
- ASorting a list
- BFinding the shortest path
- CDetermining network reliability
- DIdentifying bottlenecks in a network
13.What is the purpose of a 'source' in a flow network?
- ATo absorb flow
- BTo redirect flow
- CTo split flow
- DTo generate flow
14.In a flow network, what is a 'sink'?
- AA node that splits flow
- BA node that redirects flow
- CA node that absorbs flow
- DA node that generates flow
15.What is the significance of a 'bottleneck' in a flow network?
- AIt increases flow
- BIt decreases flow
- CIt redirects flow
- DIt has no effect on flow