image/svg+xml
Math3012AppliedCombinatorics
Goal:Finding minimalweight walksNetwork Flows
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
What's the least weight closed walkthat contains every vertex?
Traveling Salesman
NP-complete
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
5
5
10
10
1
1
1
1
b
c
f
e
t
s
1
1
0
1
1
1
1
2
flow
symmetricadjacencymatrix
anyadjacencymatrix
antisymmetricadjacencymatrix
flow value/volume
local conservation
Is there a Hamiltonian cyclewith weight less than c?
How hard am I?
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