Basics of Network Flow and Matching Algorithms
An introductory quiz on network flow and matching algorithms for backend developers.
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.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.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.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.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.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.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.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.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.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.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.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.What is the time complexity of the Edmonds-Karp algorithm?
- AO(E^2)
- BO(VE)
- CO(V^2)
- DO(V^3)
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.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.Which data structure is commonly used in the Edmonds-Karp algorithm to find augmenting paths?
- ALinked List
- BStack
- CQueue
- DPriority Queue