Introduction to Max Flow & Min Cut Algorithms
A beginner's quiz on understanding Max Flow and Min Cut algorithms in graph theory.
Questions in this quiz
15 questions on Introduction to Max Flow & Min Cut Algorithms. Work through them here, then start the quiz to answer them and see your score.
1.What is the primary goal of the Max Flow algorithm?
- ATo find the longest path in a graph
- BTo find the shortest path in a graph
- CTo find the maximum flow from a source to a sink
- DTo find the minimum spanning tree
2.Which algorithm is commonly used to solve the Max Flow problem?
- ADijkstra's Algorithm
- BKruskal's Algorithm
- CPrim's Algorithm
- DFord-Fulkerson Algorithm
3.In the context of flow networks, what does a 'cut' refer to?
- AA single node in the graph
- BA path from source to sink
- CA cycle in the graph
- DA division of the graph into two disjoint subsets
4.What does the Min Cut theorem state?
- AThe minimum cut is the longest path
- BThe minimum cut equals the maximum flow in a network
- CThe minimum cut is equal to the number of nodes
- DThe minimum cut is always zero
5.Which of the following is NOT a characteristic of a flow network?
- AIt is a directed graph
- BIt must be a tree
- CIt has a source and a sink
- DEdges have capacities
6.What is the initial step in the Ford-Fulkerson method?
- AFind a minimum spanning tree
- BFind a path with maximum capacity
- CInitialize flow to zero
- DCalculate the shortest path
7.What is an 'augmenting path' in the context of Max Flow?
- AA path that decreases the flow
- BA path that increases the flow
- CA path with no flow
- DA path that is part of a cycle
8.Which data structure is often used to find augmenting paths in the Ford-Fulkerson algorithm?
- AQueue
- BPriority Queue
- CBinary Tree
- DStack
9.What happens to the flow value when an augmenting path is found?
- AIt decreases
- BIt increases
- CIt becomes zero
- DIt remains the same
10.What is the time complexity of the Ford-Fulkerson algorithm using the Edmonds-Karp implementation?
- AO(E log V)
- BO(VE^2)
- CO(V^2E)
- DO(V + E)
11.In a flow network, what is the capacity of an edge?
- AThe average flow it can carry
- BThe minimum flow it can carry
- CThe maximum flow it can carry
- DThe total flow it has carried
12.What does the term 'residual capacity' refer to in a flow network?
- AThe capacity of the original network
- BThe capacity of the minimum cut
- CThe remaining capacity after flow is applied
- DThe total capacity of the network
13.Which of the following is a necessary condition for a flow to be valid in a flow network?
- AFlow must be non-negative
- BFlow must exceed capacity
- CFlow must be negative
- DFlow must equal capacity
14.What is the purpose of the residual graph in the Max Flow problem?
- ATo find the shortest path
- BTo determine the longest path
- CTo calculate the minimum spanning tree
- DTo track remaining capacities and reverse flows
15.In the context of Max Flow, what is a 'bottleneck'?
- AA node with maximum incoming flow
- BA node with no outgoing edges
- CAn edge with zero capacity
- DAn edge that limits the flow in an augmenting path