QuizzesIntroduction to Network Flow & Matching Algorithms
beginner
dsa

Introduction to Network Flow & Matching Algorithms

Explore the basics of network flow and matching 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 Network Flow & 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 method?

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

    • AA node where flow enters the network
    • BA node with no outgoing edges
    • CA node with no incoming edges
    • DA node where flow exits the network
  3. 3.What is the 'sink' in a flow network?

    • AA node with no incoming edges
    • BA node where flow exits the network
    • CA node with no outgoing edges
    • DA node where flow enters the network
  4. 4.Which algorithm is commonly used to find maximum bipartite matching?

    • ADijkstra's Algorithm
    • BPrim's Algorithm
    • CKruskal's Algorithm
    • DHungarian Algorithm
  5. 5.What is an augmenting path in the context of network flow?

    • AA path that increases the flow in the network
    • BA path that decreases the flow in the network
    • CA path that forms a cycle
    • DA path that has zero flow
  6. 6.In the context of network flow, what does 'capacity' refer to?

    • AThe total number of edges in the network
    • BThe maximum flow a path can handle
    • CThe maximum number of nodes in the network
    • DThe minimum flow in the network
  7. 7.What is the purpose of the Edmonds-Karp algorithm?

    • ATo find the maximum flow using BFS
    • BTo detect cycles in a graph
    • CTo find the minimum spanning tree
    • DTo find the shortest path in a graph
  8. 8.What is a residual graph?

    • AA graph with reversed edges
    • BA graph with no edges
    • CA graph with all edges doubled
    • DA graph showing remaining capacities after flow
  9. 9.What is the main characteristic of a bipartite graph?

    • AIt has cycles
    • BIt has weighted edges
    • CIt can be divided into two sets with no edges within the same set
    • DIt has directed edges
  10. 10.Which of the following is a property of maximum flow in a network?

    • AIt is always equal to the number of edges
    • BIt is always zero
    • CIt is always equal to the number of nodes
    • DIt is equal to the capacity of the minimum cut
  11. 11.What does the term 'matching' refer to in graph theory?

    • AA set of nodes without common edges
    • BA set of edges without common vertices
    • CA set of nodes with common edges
    • DA set of edges with common vertices
  12. 12.What is the time complexity of the Ford-Fulkerson method in the worst case?

    • AO(V + E)
    • BO(VE^2)
    • CO(E^2)
    • DO(E log V)
  13. 13.Which of the following is NOT a characteristic of a flow network?

    • AFlow can be negative
    • BFlow conservation at intermediate nodes
    • CHas a source and a sink
    • DAll edges have capacities
  14. 14.What is the primary application of network flow algorithms?

    • AFinding connected components
    • BDetecting cycles
    • CSolving scheduling problems
    • DFinding shortest paths
  15. 15.Which algorithm is used to find a maximum matching in a general graph?

    • ADijkstra's Algorithm
    • BEdmonds' Blossom Algorithm
    • CBellman-Ford Algorithm
    • DKruskal's Algorithm