QuizzesBasics of Network Flow and Matching Algorithms
beginner
dsa

Basics of Network Flow and Matching Algorithms

An introductory quiz on network flow and matching algorithms for backend developers.

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 Basics of Network Flow and Matching 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 Ford-Fulkerson algorithm?

    • ATo find the minimum spanning tree
    • BTo find the shortest path in a graph
    • CTo find the longest path in a graph
    • DTo find the maximum flow in a flow network
  2. 2.In a flow network, what does a 'source' node represent?

    • AA node that receives flow
    • BA node that sends flow
    • CA node with no incoming edges
    • DA node with no outgoing edges
  3. 3.What is the purpose of the Edmonds-Karp algorithm?

    • ATo find the maximum flow using BFS
    • BTo find the minimum cut
    • CTo find the longest path in a graph
    • DTo find the shortest path in a graph
  4. 4.Which of the following is a characteristic of a bipartite graph?

    • ANodes can be divided into two disjoint sets
    • BIt contains cycles
    • CAll nodes are connected to each other
    • DIt is always a tree
  5. 5.What is the main objective of the Hopcroft-Karp algorithm?

    • ATo find the maximum matching in a bipartite graph
    • BTo find the minimum spanning tree
    • CTo find the shortest path in a graph
    • DTo find the maximum flow in a flow network
  6. 6.What does the 'cut' in a flow network represent?

    • AA cycle in the graph
    • BThe maximum flow
    • CA partition of the vertices
    • DThe minimum flow
  7. 7.Which algorithm is used to find the minimum cut in a flow network?

    • AKruskal's algorithm
    • BPrim's algorithm
    • CDijkstra's algorithm
    • DFord-Fulkerson algorithm
  8. 8.What is an augmenting path in the context of network flow?

    • AA path that decreases the flow
    • BA path with no flow
    • CA path that increases the flow
    • DA path that forms a cycle
  9. 9.In network flow, what is the 'sink' node?

    • AA node with no outgoing edges
    • BA node that receives flow
    • CA node that sends flow
    • DA node with no incoming edges
  10. 10.Which of the following is true about the residual graph?

    • AIt contains only the source and sink
    • BIt contains only the original capacities
    • CIt is a subgraph of the original graph
    • DIt shows the remaining capacity for each edge
  11. 11.What does the term 'matching' refer to in graph theory?

    • AA path that visits every vertex
    • BA cycle that visits every vertex
    • CA set of edges with no common vertices
    • DA complete subgraph
  12. 12.What is the time complexity of the Edmonds-Karp algorithm?

    • AO(E^2)
    • BO(VE)
    • CO(V^2)
    • DO(V^3)
  13. 13.In a bipartite graph, what is a 'perfect matching'?

    • AA matching that forms a cycle
    • BA matching with the maximum number of edges
    • CA matching that covers all vertices
    • DA matching with no edges
  14. 14.What is the relationship between maximum flow and minimum cut in a flow network?

    • AMaximum flow is always less than minimum cut
    • BMaximum flow equals minimum cut
    • CMaximum flow is always greater than minimum cut
    • DThere is no relationship
  15. 15.Which data structure is commonly used in the Edmonds-Karp algorithm to find augmenting paths?

    • ALinked List
    • BStack
    • CQueue
    • DPriority Queue