QuizzesIntroduction to Network Flows & Cuts in Graph Theory
beginner
dsa

Introduction to Network Flows & Cuts in Graph Theory

Explore the basics of network flows and cuts 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 Flows & Cuts in Graph Theory. 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 Min-Cut Theorem?

    • ATo find the minimum spanning tree
    • BTo find the shortest path in a network
    • CTo calculate the network's capacity
    • DTo find the maximum flow in a network
  2. 2.In a flow network, what does a 'cut' represent?

    • AA cycle in the network
    • BThe shortest path between two nodes
    • CThe longest path in the network
    • DA partition of the network into two disjoint subsets
  3. 3.Which algorithm is commonly used to find the maximum flow in a network?

    • APrim's Algorithm
    • BDijkstra's Algorithm
    • CFord-Fulkerson Algorithm
    • DKruskal's Algorithm
  4. 4.What is the capacity of an edge in a flow network?

    • AThe maximum flow that can pass through the edge
    • BThe cost associated with the edge
    • CThe minimum flow required through the edge
    • DThe length of the edge
  5. 5.In the context of network flows, what is a 'sink'?

    • AA node with no incoming edges
    • BA node where flow originates
    • CA node where flow is absorbed
    • DA node with no outgoing edges
  6. 6.What does the term 'augmenting path' refer to in network flows?

    • AA path that increases the flow
    • BA path with zero flow
    • CA path with maximum capacity
    • DA path that decreases the flow
  7. 7.Which of the following is NOT a characteristic of a flow network?

    • ADirected edges
    • BCapacities on edges
    • CA source and a sink
    • DUndirected edges
  8. 8.What is the flow conservation property in a flow network?

    • AFlow into a node is greater than flow out
    • BFlow into a node equals flow out of the node
    • CFlow into a node is zero
    • DFlow into a node is less than flow out
  9. 9.In a flow network, what is the significance of a 'bottleneck' edge?

    • AIt limits the maximum flow
    • BIt increases the maximum flow
    • CIt is the longest edge
    • DIt has zero capacity
  10. 10.What does the Edmonds-Karp algorithm improve upon the Ford-Fulkerson method?

    • AIt uses dynamic programming
    • BIt uses breadth-first search
    • CIt uses depth-first search
    • DIt uses a greedy approach
  11. 11.What is the time complexity of the Edmonds-Karp algorithm?

    • AO(E log V)
    • BO(V^2E)
    • CO(V + E)
    • DO(VE^2)
  12. 12.What is a residual graph in the context of network flows?

    • AA graph showing longest paths
    • BA graph showing shortest paths
    • CA graph showing remaining capacities
    • DA graph showing used capacities
  13. 13.What does the term 'cut-set' refer to in a flow network?

    • AA set of edges with maximum capacity
    • BA set of nodes with zero flow
    • CA set of edges that, if removed, disconnects the source from the sink
    • DA set of nodes that forms a cycle
  14. 14.Which property must hold true for a flow to be valid in a network?

    • AFlow must be negative
    • BFlow must not exceed edge capacities
    • CFlow must exceed edge capacities
    • DFlow must be zero
  15. 15.In a flow network, what is the purpose of a 'source' node?

    • ATo initiate the flow
    • BTo terminate the flow
    • CTo balance the flow
    • DTo store the flow