image/svg+xml
a
b
c
d
e
f
1
1
1
1
5
5
10
10
What's the least weight closed walk thattraverses every edge?
Kwan's Postman Problem
Use Dijkstra to compute weightsof paths between all odd degree vertices.Double edges in a minimal pairing.Find Eulerian circuit of the resulting multigraph
weightedgraph
a
b
c
d
e
f
a
b
c
d
e
f
1
5
5
10
10
1
1
1
1
1
1
2
6
10
7
10
1
1
8
1
5
5
4
5
weighteddigraph
a
b
c
d
e
f
5
5
10
10
1
1
1
1
weightedorientedgraph
5
5
10
10
1
1
1
1
b
c
f
e
t
s
(flow) network
sourcesinkcapacity
symmetricadjacencymatrix
anyadjacencymatrix
antisymmetricadjacencymatrix
How hard am I?
Math3012AppliedCombinatorics
Goal:ConstructingMaximal Flows
Â
5
5
10
10
1
1
1
1
b
c
f
e
t
s
(flow) network
sourcesinkcapacity
5
5
10
10
1
1
1
1
b
c
f
e
t
s
1
1
0
1
1
1
1
2
flow
flow value/volume
local conservation
5
5
10
10
1
1
1
1
b
c
f
e
t
s
1
1
0
1
1
1
1
cut
cut capacity
Max Flow Min Cut Theorem
The maximum value of any flow isequal to the minimum capacity ofany cut.
2
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?Â
5
5
7
10
3
4
6
5
b
c
f
e
t
s
Augmenting PathÂ
slack
Ford Fulkerson
0
4
3
4
4
1
1
0
scbft
secbt
slack 3
slack 2
1
3
4
5
2
8
6
7
3
2
2
8
4
5
s
t
Factory produces 15 tons of flugelsStore 2 demands 7 tonsStore 5 demands 8 tonsÂ
8
7
5
5
10
10
1
1
1
1
b
c
f
e
t
s
1
1
0
1
1
1
1
2
15
What complexity is the Network Flow Problem?
106
106
106
106
1
0
1
s
t
Edmund's Karp Algorithm
'Ford-Fulkerson labeling'
Construct augmenting paths bybreadth first search
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
Find a maximal set of edge disjoint paths
s
t
Menger's Messengers