QuizzesIntroduction to Max Flow & Min Cut Algorithms
beginner
dsa

Introduction to Max Flow & Min Cut Algorithms

A beginner's quiz on understanding Max Flow and Min Cut algorithms in graph theory.

15 minutes 15 questions Pass at 70%
Time Limit
15 minutes - timer starts when you begin
Change Answers Freely
Revisit and change any answer before submitting
Full Review After Submit
Correct answers and explanations shown for every question
Auto-submit on timeout
Quiz submits automatically when time runs out

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. 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. 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. 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. 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. 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. 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. 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. 8.Which data structure is often used to find augmenting paths in the Ford-Fulkerson algorithm?

    • AQueue
    • BPriority Queue
    • CBinary Tree
    • DStack
  9. 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. 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. 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. 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. 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. 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. 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