Network Flow and Ford-Fulkerson Fundamentals Quiz Quiz

Challenge your understanding of network flow principles and the Ford-Fulkerson algorithm with this beginner-friendly quiz. Review essential terms, concepts, and problem-solving techniques related to maximum flow, residual graphs, augmenting paths, and more.

1. Definition of Flow Network

   Which statement best describes a flow network in network flow theory?

   1. An undirected graph with arbitrary edge weights and no specific nodes
   2. A network where all nodes have the same degree
   3. A graph without capacities or restrictions on the flow
   4. A directed graph where each edge has a capacity and two special nodes called source and sink

   Explanation: A flow network is a directed graph in which each edge has a capacity, and there is a designated source and sink node through which flow enters and exits. Option B describes an undirected graph, which does not fit the flow network definition. Option C ignores capacities and special nodes, which are vital to flow networks. Option D is incorrect since node degrees are not relevant to the definition.

2. Purpose of Ford-Fulkerson Algorithm

   What primary problem does the Ford-Fulkerson method solve in network flow?

   1. It finds the shortest path between two nodes
   2. It computes the maximum flow from source to sink in a flow network
   3. It determines the graph’s chromatic number
   4. It calculates the minimum spanning tree of the graph

   Explanation: Ford-Fulkerson is designed to find the maximum possible flow from the source to sink in a flow network. Finding shortest paths (option B) or minimum spanning trees (option C) are different graph problems solved by other algorithms. The chromatic number (option D) relates to graph coloring, not flows.

3. Residual Graph Construction

   In the context of Ford-Fulkerson, what is a residual graph?

   1. A duplicate of the original graph for backup purposes
   2. A graph showing the remaining capacities after some flow has been sent
   3. A subgraph containing only nodes of degree two
   4. A tree structure representing the spanning tree

   Explanation: The residual graph represents how much more flow can be sent through each edge after accounting for current flows. Option B refers to an unnecessary duplicate for this purpose. The spanning tree structure (option C) and a subgraph of degree-two nodes (option D) are unrelated to residual graphs in this context.

4. Augmenting Paths Definition

   When using Ford-Fulkerson, what is an augmenting path?

   1. A loop that returns to the source node
   2. A shortest path determined by edge count
   3. A path containing only backward edges
   4. A path from source to sink where the residual capacity of every edge is positive

   Explanation: An augmenting path connects source to sink with available capacity along every edge in the residual graph. Option B describes a cycle, not a path from source to sink. Option C mentions only backward edges, which is insufficient. Option D restricts the definition to shortest paths, though any available path suffices.

5. Edge Saturation in Flow Networks

   What does it mean when an edge is 'saturated' in a flow network?

   1. The current flow equals the edge's capacity
   2. There are no more paths through the edge
   3. The edge has zero capacity left
   4. The edge is part of a cycle

   Explanation: An edge is saturated when the flow on it reaches its maximum allowed capacity. Option B is misleading; while capacity is fully used, saturation is defined by maximum possible flow, not zero capacity. Being part of a cycle (option C) is unrelated. Option D is inaccurate as paths are independent of saturation.

6. Termination Condition of Ford-Fulkerson

   According to the Ford-Fulkerson algorithm, when should the process of finding augmenting paths stop?

   1. When there are no more augmenting paths from source to sink in the residual graph
   2. When the flow value is zero
   3. When all edges are saturated in the network
   4. When the minimum cut is achieved

   Explanation: Ford-Fulkerson terminates when no more augmenting paths exist, meaning no additional flow can reach the sink. Option B is incorrect because not all edges must be saturated. Option C refers to the cut, which is related but does not define the stopping rule. Option D is incorrect as we aim for maximum, not zero, flow.

7. Initial Flow in Ford-Fulkerson

   What is the initial flow on all edges when starting the Ford-Fulkerson algorithm?

   1. Negative flow values
   2. Randomly assigned values
   3. Maximum flow on all edges
   4. Zero flow on all edges

   Explanation: The algorithm starts with zero flow everywhere, gradually increasing it through augmentations. Assigning maximum flow initially (option B) is not allowed. Random values (option C) would not be valid. Negative flows (option D) are not permitted in network flow.

8. Maximum Flow-Minimum Cut Theorem

   Which statement describes the relationship between maximum flow and minimum cut in a flow network?

   1. The minimum cut is unrelated to the flow value
   2. The maximum flow value equals the minimum cut capacity
   3. The minimum cut always includes every edge
   4. The maximum flow is always less than the minimum cut

   Explanation: The max-flow min-cut theorem states that the maximum value of flow from source to sink equals the capacity of the smallest cut. Option B is incorrect, as they're equal. Option C and D are both incorrect, as the minimum cut is intrinsically linked to flow and does not require all edges.

9. Integral Flows in Networks

   In a network with all integer capacities, what type of flow values does the Ford-Fulkerson algorithm (using BFS or DFS) produce?

   1. Some flows may be fractions
   2. All flow values will be integers
   3. All flows must be zero
   4. All flows will be negative integers

   Explanation: When all capacities are integers, the algorithm augments flow by integer amounts, resulting in only integer flows. Fractional flows (option B) can occur with non-integral capacities, not here. Option C is false once augmentation starts. Negative flows (option D) violate the flow direction rule.

10. Limitation of Ford-Fulkerson Algorithm

    Which of the following is a known limitation of the original Ford-Fulkerson algorithm?

    1. It may not terminate on graphs with irrational capacities
    2. It always produces suboptimal flows
    3. It cannot handle graphs with integer capacities
    4. It only works with undirected graphs

    Explanation: Original Ford-Fulkerson can enter infinite loops with irrational capacities, never converging. Option B is incorrect since the algorithm is for directed graphs. Option C is false as integer capacities are ideal. Option D is wrong since the algorithm does output optimal flows for suitable input.