Introduction to Network Flow & Matching Algorithms
Explore the basics of network flow and matching algorithms in graph theory.
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.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.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.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.Which algorithm is commonly used to find maximum bipartite matching?
- ADijkstra's Algorithm
- BPrim's Algorithm
- CKruskal's Algorithm
- DHungarian Algorithm
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.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.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.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.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.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.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.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.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.What is the primary application of network flow algorithms?
- AFinding connected components
- BDetecting cycles
- CSolving scheduling problems
- DFinding shortest paths
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