Graphs and Networks 1 (AQA A-Level Further Maths): Flashcards

Maximum possible flow along an arc

Node where flow enters; all arcs directed away from it

Node where flow exits; all arcs directed towards it

Flow in an arc $\leq$ capacity

At intermediate nodes: total inflow = total outflow

Total outflow from S = total inflow to T

Arc where flow = capacity (at full capacity)

Arc where flow < capacity (has spare capacity)

Set of arcs separating S and T when removed

Max flow value = min cut capacity