Introduction to Network Flows & Cuts in Graph Theory
Explore the basics of network flows and cuts in graph theory.
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.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.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.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.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.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.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.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.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.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.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.What is the time complexity of the Edmonds-Karp algorithm?
- AO(E log V)
- BO(V^2E)
- CO(V + E)
- DO(VE^2)
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.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.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.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