Max Flow Problems

Flashcards covering key vocabulary and concepts related to Max Flow Problems as discussed in Chapter 7.

Max Flow Problems

A category of network flow problems that focus on determining the maximum flow through a flow network between a source and a sink.

Flow Capacity

The maximum amount of flow that can pass through an arc in a network.

Source Node

The starting point in a flow network where flow originates.

Sink Node

The endpoint in a flow network where flow is supposed to exit.

Residual Graph

A graph that shows the available flow capacities remaining after some flow has been assigned to the arcs.

Breakthrough

A path in the network that allows additional flow to be pushed from the source to the sink.

Ford-Fulkerson Algorithm

A method for computing the maximum flow in a flow network by searching for augmenting paths.

In=Out Constraint

A constraint that ensures the flow entering a node equals the flow exiting the node (flow conservation) in a flow network.

Return Arc

An arc in a modified flow model that circulates flow from the sink back to the source to simplify the model.

Max Flow LP Formulation

The linear programming model that represents the maximum flow problem including decision variables, objective function, and constraints.