image/svg+xml
Math3012AppliedCombinatorics
Goal:How can we applyflow networks?
(flow) network
sourcesinkcapacity
5
5
10
10
6
2
1
7
b
c
f
e
t
s
1
1
3
4
4
1
1
5
flow
Max Flow Min Cut Theorem
The maximum value of any flow isequal to the minimum capacity ofany cut.
1
3
4
5
2
8
6
7
3
2
2
8
4
5
Supply Chain Problems
Factory produces 15 tons of flugels.Store 2 demands 7 tons.Store 5 demands 8 tons.Distributors and their capacities are shown.How do we optimize the flow?Should Flugel, Inc., invest in factories, distribution, or marketing?
1
3
4
5
2
8
6
7
3
2
2
8
4
5
s
t
8
7
15
secbt augmenting path slack 3
({s,e,c},{b,f,t}) cut capacity 5
BurbageFlitwickHoochLockharteMcGonagallQuirrellSlughornSnapeSproutTrelawneyVector
ArithmancyCharmsDefense Against Dark ArtsDivinationFlyingHerbologyMuggle StudiesPotionsTransfiguration
Applicants
Positions
Qualifications
How should we hire to maximize the number of filled positions?
Matching
MaximalMatching
PerfectMatching
s
t
All edges capacity 1
Maximum flow gives a maximal matching
The most flow without going over capacity
Find a maximal set of edge disjoint paths
s
t
Menger's Messengers