Determine and certify maximum flow
Consider the directed network for a server-request network. The source is W and the sink is Y. Each edge label is its capacity in requests/s. The network transfers requests each second; intermediate vertices pass on all incoming flow
Use inspection to allocate a feasible flow before checking its upper bound
The table specifies one particular feasible-flow certificate, not every possible feasible flow. Keep each displayed flow fixed and determine only the question-mark entries using conservation. Flow and capacity use the same units shown above. The diagram labels are capacities, not assigned flows
| Directed edge | Capacity | Assigned flow |
|---|---|---|
| W→D1 | 20 | 20 |
| D1→H | 40 | 20 |
| H→O | 50 | 20 |
| O→Y | 30 | 20 |
| W→F1 | 50 | ? |
| F1→Y | 80 | 50 |
| W→I | 50 | ? |
| I→E1 | 80 | 50 |
| E1→Y | 60 | 50 |