Sign inSign in

Max-flow min-cut theorem

The theorem stating that the maximum flow in a network is equal to the capacity of the minimum cut.
as Srini Devadas defines itMITThe wording closest to all 4 definitions
Watch it explained

Know first

Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.

Opens up

Concepts that name this one as a prerequisite.

Lecturers

3

Each in their own terms, from the easiest level.

  • Srini Devadas

    MIT · Undergraduate

    A theorem stating that the maximum value of a flow in a network is equal to the capacity of the minimum cut.
    • 17:00Incremental Improvement: Matching
  • Ryan O'Donnell

    Carnegie Mellon University · Undergraduate

    The principle stating that the maximum flow through a network is equal to the capacity of the minimum cut separating the source and sink.
    • 15:54Min-st-Cut is the Dual LP of Max-st-Flow
  • Gilbert Strang

    MIT · Undergraduate

    The theorem stating that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the total capacity of the minimum cut that separates the source from the sink.
    • 24:32Linear Programming and Two-Person Games

Lectures that assume it

1

Connections

14

The lectures that define it or assume it, and the concepts next to it.

3 lecturers. Definitions are written by AI from each lecture’s transcript. A time with a play mark starts the lecture at the moment the lecturer says it.