image/svg+xml
Math3012AppliedCombinatorics
Goal:Minimal WeightSubgraphs
JFK
ORD
LHR
SEA
LAX
IAH
ATL
CDG
HND
10
7
12
9
8
3
4
7
11
10
4
3
3
10
9
5
4
5
7
Â
What's the cheapest way to connectevery city?
weighted graph
minimal spanning tree
Kruskal's Algorithm (No cycles)
a
b
c
d
e
g
i
f
h
j
k
15
4
3
10
3
2
8
7
6
1
1
3
1
2
3
5
What's the least weight path from a to k?
9
8
8
Dijkstra's Algorithm
Â
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 closedwalk that 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 closed spanningwalk with 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 over all flows isequal to the minimum capacity overall cuts.
2
always add the leastweight edge that doesn'tmake a cycle
3,3,3,4,4,4,5,5,7,7,7,8,9,9,10,10,10,11,12