Advanced Graph Algorithms: Network Flow & Applications
Test your understanding of network flow algorithms and their applications in backend systems.
Questions in this quiz
12 questions on Advanced Graph Algorithms: Network Flow & Applications. 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 in network flow problems?
- ATo find the shortest path between two nodes
- BTo find the minimum spanning tree
- CTo detect cycles in a graph
- DTo find the maximum flow in a flow network
2.Which of the following is a key assumption of the Edmonds-Karp algorithm?
- AIt uses breadth-first search to find augmenting paths
- BIt assumes all capacities are integers
- CIt uses depth-first search to find augmenting paths
- DIt requires the graph to be acyclic
3.In a flow network, what does the 'capacity constraint' refer to?
- AThe sum of incoming flows must equal the sum of outgoing flows
- BFlow on an edge cannot exceed its capacity
- CThe network must have a single source and sink
- DThe total flow must equal the total capacity
4.What is the purpose of a residual graph in network flow algorithms?
- ATo detect cycles in the network
- BTo track the shortest path
- CTo find augmenting paths by showing remaining capacities
- DTo represent the original graph
5.Which algorithm is commonly used to solve the 'minimum cut' problem in a flow network?
- APrim's algorithm
- BFord-Fulkerson algorithm
- CKruskal's algorithm
- DDijkstra's algorithm
6.In the context of network flow, what is an 'augmenting path'?
- AA path that connects all nodes in the network
- BA path that can increase the flow from source to sink
- CA path that increases the total capacity of the network
- DA path that decreases the flow in the network
7.Why is the Dinic's algorithm considered efficient for network flow problems?
- AIt is based on dynamic programming
- BIt uses depth-first search
- CIt uses a greedy approach
- DIt finds multiple augmenting paths simultaneously
8.What is the significance of the 'cut' in a flow network?
- AIt divides the network into two disjoint subsets
- BIt is used to find cycles
- CIt represents the shortest path
- DIt indicates the maximum flow
9.Which problem can be solved using the concept of network flow?
- AMinimum Spanning Tree
- BTraveling Salesman Problem
- CBipartite Matching
- DGraph Coloring
10.What is the time complexity of the Edmonds-Karp algorithm?
- AO(V^2)
- BO(V + E)
- CO(VE^2)
- DO(V^3)
11.In a flow network, what is the 'source' node?
- AA node with no outgoing edges
- BThe node where flow terminates
- CThe node where flow originates
- DA node with no incoming edges
12.How does the push-relabel algorithm differ from the Ford-Fulkerson method?
- AIt requires integer capacities
- BIt uses depth-first search
- CIt maintains a preflow instead of a flow
- DIt uses augmenting paths