Courses

# Maximum Flow (2) Notes | EduRev

## : Maximum Flow (2) Notes | EduRev

``` Page 1

Princeton University  •  COS 423  •  Theory of Algorithms  •  Spring 2002  •  Kevin Wayne
MST:  Red Rule, Blue Rule
Some of these lecture slides are adapted from material in:
• Data Structures and Algorithms, R. E. Tarjan.
• Randomized Algorithms, R. Motwani and P. Raghavan.
2
Cycles and Cuts
Cycle.
¦ A cycle is a set of arcs of the form {a,b}, {b,c}, {c,d}, . . ., {z,a}.
Cut.
¦ The cut induced by a subset of nodes S is the set of all arcs with
exactly one endpoint in S.
Path = 1-2-3-4-5-6-1
Cycle = {1, 2}, {2, 3}, {3, 4},
{4, 5}, {5, 6}, {6, 1}
1
3
8
2
6
7
4
5
S = {4, 5, 6}
Cut = {5, 6}, {5, 7}, {3, 4},
{3, 5}, {7, 8}
1
3
8
2
6
7
4
5
3
Cycle-Cut Intersection
A cycle and a cut intersect in an even number of arcs.
Proof.
1
3
8
2
6
7
4
5
S
V - S
C
Intersection = {3, 4}, {5, 6}
4
Spanning Tree
Spanning tree.  Let T = (V, F) be a subgraph of G = (V, E).  TFAE:
¦ T is a spanning tree of G.
¦ T is acyclic and connected.
¦ T is connected and has |V| - 1 arcs.
¦ T is acyclic and has |V| - 1 arcs.
¦ T is minimally connected: removal of any arc disconnects it.
¦ T is maximally acyclic: addition of any arc creates a cycle.
¦ T has a unique simple path between every pair of vertices.
1
3
8
2
6
7
4
5
1
3
8
2
6
7
4
5
G = (V, E)
T = (V, F)
Page 2

Princeton University  •  COS 423  •  Theory of Algorithms  •  Spring 2002  •  Kevin Wayne
MST:  Red Rule, Blue Rule
Some of these lecture slides are adapted from material in:
• Data Structures and Algorithms, R. E. Tarjan.
• Randomized Algorithms, R. Motwani and P. Raghavan.
2
Cycles and Cuts
Cycle.
¦ A cycle is a set of arcs of the form {a,b}, {b,c}, {c,d}, . . ., {z,a}.
Cut.
¦ The cut induced by a subset of nodes S is the set of all arcs with
exactly one endpoint in S.
Path = 1-2-3-4-5-6-1
Cycle = {1, 2}, {2, 3}, {3, 4},
{4, 5}, {5, 6}, {6, 1}
1
3
8
2
6
7
4
5
S = {4, 5, 6}
Cut = {5, 6}, {5, 7}, {3, 4},
{3, 5}, {7, 8}
1
3
8
2
6
7
4
5
3
Cycle-Cut Intersection
A cycle and a cut intersect in an even number of arcs.
Proof.
1
3
8
2
6
7
4
5
S
V - S
C
Intersection = {3, 4}, {5, 6}
4
Spanning Tree
Spanning tree.  Let T = (V, F) be a subgraph of G = (V, E).  TFAE:
¦ T is a spanning tree of G.
¦ T is acyclic and connected.
¦ T is connected and has |V| - 1 arcs.
¦ T is acyclic and has |V| - 1 arcs.
¦ T is minimally connected: removal of any arc disconnects it.
¦ T is maximally acyclic: addition of any arc creates a cycle.
¦ T has a unique simple path between every pair of vertices.
1
3
8
2
6
7
4
5
1
3
8
2
6
7
4
5
G = (V, E)
T = (V, F)
5
Minimum Spanning Tree
Minimum spanning tree. Given connected graph G with real-valued
arc weights c
e
, an MST is a spanning tree of G whose sum of arc
weights is minimized.
Cayley’s Theorem (1889). There are n
n-2
spanning trees of K
n
.
¦ n = |V|, m = |E|.
¦ Can’t solve MST by brute force.
1
3
8
2
6
7
4
5
5
23
10
21
14
24
16
6
4
18
9
7
11
8
1
3
8
2
6
7
4
5
5
6
4
9
7
11
8
G = (V, E) T = (V, F)
w(T) = 50
6
Applications
MST is central combinatorial problem with divserse applications.
¦ Designing physical networks.
– telephone, electrical, hydraulic, TV cable, computer, road
¦ Cluster analysis.
– delete long edges leaves connected components
– finding clusters of quasars and Seyfert galaxies
– analyzing fungal spore spatial patterns
¦ Approximate solutions to NP-hard problems.
– metric TSP, Steiner tree
¦ Indirect applications.
– describing arrangements of nuclei in skin cells for cancer research
– learning salient features for real-time face verification
– modeling locality of particle interactions in turbulent fluid flow
– reducing data storage in sequencing amino acids in a protein
7
Optimal Message Passing
Optimal message passing.
¦ Distribute message to N agents.
¦ Each agent can communicate with some of the other agents, but their
communication is (independently) detected with probability p
ij
.
¦ Group leader wants to transmit message (e.g., Divx movie)  to all
agents so as to minimize the total probability that message is detected.
Objective.
¦ Find tree T that minimizes:
¦ Or equivalently, that maximizes:
¦ Or equivalently, that maximizes:
¦ Or equivalently, MST with weights p
ij
.
1- 1- p
ij ( )
(i,j)? T
1- p
ij ( )
(i,j)? T
log 1- p
ij ( )
(i,j)? T
8
Fundamental Cycle
Fundamental cycle.
¦ Adding any non-tree arc e to T forms unique cycle C.
¦ Deleting any arc f ? C from T ¨ {e} results in new spanning tree.
Cycle optimality conditions: For every non-tree arc e, and for every
tree arc f in its fundamental cycle:  c
f
£ c
e
.
Observation: If c
f
> c
e
then T is not a MST.
1
3
8
2
6
7
4
5
f
e
9
Page 3

Princeton University  •  COS 423  •  Theory of Algorithms  •  Spring 2002  •  Kevin Wayne
MST:  Red Rule, Blue Rule
Some of these lecture slides are adapted from material in:
• Data Structures and Algorithms, R. E. Tarjan.
• Randomized Algorithms, R. Motwani and P. Raghavan.
2
Cycles and Cuts
Cycle.
¦ A cycle is a set of arcs of the form {a,b}, {b,c}, {c,d}, . . ., {z,a}.
Cut.
¦ The cut induced by a subset of nodes S is the set of all arcs with
exactly one endpoint in S.
Path = 1-2-3-4-5-6-1
Cycle = {1, 2}, {2, 3}, {3, 4},
{4, 5}, {5, 6}, {6, 1}
1
3
8
2
6
7
4
5
S = {4, 5, 6}
Cut = {5, 6}, {5, 7}, {3, 4},
{3, 5}, {7, 8}
1
3
8
2
6
7
4
5
3
Cycle-Cut Intersection
A cycle and a cut intersect in an even number of arcs.
Proof.
1
3
8
2
6
7
4
5
S
V - S
C
Intersection = {3, 4}, {5, 6}
4
Spanning Tree
Spanning tree.  Let T = (V, F) be a subgraph of G = (V, E).  TFAE:
¦ T is a spanning tree of G.
¦ T is acyclic and connected.
¦ T is connected and has |V| - 1 arcs.
¦ T is acyclic and has |V| - 1 arcs.
¦ T is minimally connected: removal of any arc disconnects it.
¦ T is maximally acyclic: addition of any arc creates a cycle.
¦ T has a unique simple path between every pair of vertices.
1
3
8
2
6
7
4
5
1
3
8
2
6
7
4
5
G = (V, E)
T = (V, F)
5
Minimum Spanning Tree
Minimum spanning tree. Given connected graph G with real-valued
arc weights c
e
, an MST is a spanning tree of G whose sum of arc
weights is minimized.
Cayley’s Theorem (1889). There are n
n-2
spanning trees of K
n
.
¦ n = |V|, m = |E|.
¦ Can’t solve MST by brute force.
1
3
8
2
6
7
4
5
5
23
10
21
14
24
16
6
4
18
9
7
11
8
1
3
8
2
6
7
4
5
5
6
4
9
7
11
8
G = (V, E) T = (V, F)
w(T) = 50
6
Applications
MST is central combinatorial problem with divserse applications.
¦ Designing physical networks.
– telephone, electrical, hydraulic, TV cable, computer, road
¦ Cluster analysis.
– delete long edges leaves connected components
– finding clusters of quasars and Seyfert galaxies
– analyzing fungal spore spatial patterns
¦ Approximate solutions to NP-hard problems.
– metric TSP, Steiner tree
¦ Indirect applications.
– describing arrangements of nuclei in skin cells for cancer research
– learning salient features for real-time face verification
– modeling locality of particle interactions in turbulent fluid flow
– reducing data storage in sequencing amino acids in a protein
7
Optimal Message Passing
Optimal message passing.
¦ Distribute message to N agents.
¦ Each agent can communicate with some of the other agents, but their
communication is (independently) detected with probability p
ij
.
¦ Group leader wants to transmit message (e.g., Divx movie)  to all
agents so as to minimize the total probability that message is detected.
Objective.
¦ Find tree T that minimizes:
¦ Or equivalently, that maximizes:
¦ Or equivalently, that maximizes:
¦ Or equivalently, MST with weights p
ij
.
1- 1- p
ij ( )
(i,j)? T
1- p
ij ( )
(i,j)? T
log 1- p
ij ( )
(i,j)? T
8
Fundamental Cycle
Fundamental cycle.
¦ Adding any non-tree arc e to T forms unique cycle C.
¦ Deleting any arc f ? C from T ¨ {e} results in new spanning tree.
Cycle optimality conditions: For every non-tree arc e, and for every
tree arc f in its fundamental cycle:  c
f
£ c
e
.
Observation: If c
f
> c
e
then T is not a MST.
1
3
8
2
6
7
4
5
f
e
9
9
Fundamental Cut
Fundamental cut.
¦ Deleting any tree arc f from T disconnects tree into two
components with cut D.
¦ Adding back any arc e ? D to T - {f} results in new spanning tree.
Cut optimality conditions: For every tree arc f, and for every non-tree
arc e in its fundamental cut:  c
e
‡ c
f
.
Observation: If c
e
< c
f
then T not a MST.
1
3
8
2
6
7
4
5
f
e
9
10
MST:  Cut Optimality Conditions
Theorem. Cut optimality  MST.   (proof by contradiction)
¦ T = spanning tree that satisfies cut optimality conditions.
T*  = MST that has as many arcs in common with T as possible.
¦ If T = T*, then we are done. Otherwise, let f ? T  s.t.  f ? T*.
¦ Let D be fundamental cut formed by deleting f from T.
¦ Adding f to T* creates a fund cycle C, which shares (at least) two arcs
with cut D. One is f, let e be another. Note:  e  ? T.
¦ Cut optimality conditions   c
f
£ c
e
.
¦ Thus, we can replace e with f in T* without increasing its cost.
f
T T*
e
f
e
11
MST:  Cycle Optimality Conditions
Theorem. Cut optimality  MST.   (proof by contradiction)
¦ T = spanning tree that satisfies cut optimality conditions.
T*  = MST that has as many arcs in common with T as possible.
¦ If T = T*, then we are done. Otherwise, let f ? T  s.t.  f ? T*.
¦ Let D be fundamental cut formed by deleting f from T.
¦ Adding f to T* creates a fund cycle C, which shares (at least) two arcs
with cut D. One is f, let e be another. Note:  e  ? T.
¦ Cut optimality conditions   c
f
£ c
e
.
¦ Thus, we can replace e with f in T* without increasing its cost.
f
T T*
e
f
e
Cycle
cycle
e ? T* s.t. e ? T
Deleting e from cut D
cycle C
C
e f
Cycle f ? T*
12
Towards a Generic MST Algorithm
If all arc weights are distinct:
¦ MST is unique.
¦ Arc with largest weight in cycle C is not in MST.
– cycle optimality conditions
¦ Arc with smallest weight in cutset D is in MST.
– cut optimality conditions
SS’
C
Page 4

Princeton University  •  COS 423  •  Theory of Algorithms  •  Spring 2002  •  Kevin Wayne
MST:  Red Rule, Blue Rule
Some of these lecture slides are adapted from material in:
• Data Structures and Algorithms, R. E. Tarjan.
• Randomized Algorithms, R. Motwani and P. Raghavan.
2
Cycles and Cuts
Cycle.
¦ A cycle is a set of arcs of the form {a,b}, {b,c}, {c,d}, . . ., {z,a}.
Cut.
¦ The cut induced by a subset of nodes S is the set of all arcs with
exactly one endpoint in S.
Path = 1-2-3-4-5-6-1
Cycle = {1, 2}, {2, 3}, {3, 4},
{4, 5}, {5, 6}, {6, 1}
1
3
8
2
6
7
4
5
S = {4, 5, 6}
Cut = {5, 6}, {5, 7}, {3, 4},
{3, 5}, {7, 8}
1
3
8
2
6
7
4
5
3
Cycle-Cut Intersection
A cycle and a cut intersect in an even number of arcs.
Proof.
1
3
8
2
6
7
4
5
S
V - S
C
Intersection = {3, 4}, {5, 6}
4
Spanning Tree
Spanning tree.  Let T = (V, F) be a subgraph of G = (V, E).  TFAE:
¦ T is a spanning tree of G.
¦ T is acyclic and connected.
¦ T is connected and has |V| - 1 arcs.
¦ T is acyclic and has |V| - 1 arcs.
¦ T is minimally connected: removal of any arc disconnects it.
¦ T is maximally acyclic: addition of any arc creates a cycle.
¦ T has a unique simple path between every pair of vertices.
1
3
8
2
6
7
4
5
1
3
8
2
6
7
4
5
G = (V, E)
T = (V, F)
5
Minimum Spanning Tree
Minimum spanning tree. Given connected graph G with real-valued
arc weights c
e
, an MST is a spanning tree of G whose sum of arc
weights is minimized.
Cayley’s Theorem (1889). There are n
n-2
spanning trees of K
n
.
¦ n = |V|, m = |E|.
¦ Can’t solve MST by brute force.
1
3
8
2
6
7
4
5
5
23
10
21
14
24
16
6
4
18
9
7
11
8
1
3
8
2
6
7
4
5
5
6
4
9
7
11
8
G = (V, E) T = (V, F)
w(T) = 50
6
Applications
MST is central combinatorial problem with divserse applications.
¦ Designing physical networks.
– telephone, electrical, hydraulic, TV cable, computer, road
¦ Cluster analysis.
– delete long edges leaves connected components
– finding clusters of quasars and Seyfert galaxies
– analyzing fungal spore spatial patterns
¦ Approximate solutions to NP-hard problems.
– metric TSP, Steiner tree
¦ Indirect applications.
– describing arrangements of nuclei in skin cells for cancer research
– learning salient features for real-time face verification
– modeling locality of particle interactions in turbulent fluid flow
– reducing data storage in sequencing amino acids in a protein
7
Optimal Message Passing
Optimal message passing.
¦ Distribute message to N agents.
¦ Each agent can communicate with some of the other agents, but their
communication is (independently) detected with probability p
ij
.
¦ Group leader wants to transmit message (e.g., Divx movie)  to all
agents so as to minimize the total probability that message is detected.
Objective.
¦ Find tree T that minimizes:
¦ Or equivalently, that maximizes:
¦ Or equivalently, that maximizes:
¦ Or equivalently, MST with weights p
ij
.
1- 1- p
ij ( )
(i,j)? T
1- p
ij ( )
(i,j)? T
log 1- p
ij ( )
(i,j)? T
8
Fundamental Cycle
Fundamental cycle.
¦ Adding any non-tree arc e to T forms unique cycle C.
¦ Deleting any arc f ? C from T ¨ {e} results in new spanning tree.
Cycle optimality conditions: For every non-tree arc e, and for every
tree arc f in its fundamental cycle:  c
f
£ c
e
.
Observation: If c
f
> c
e
then T is not a MST.
1
3
8
2
6
7
4
5
f
e
9
9
Fundamental Cut
Fundamental cut.
¦ Deleting any tree arc f from T disconnects tree into two
components with cut D.
¦ Adding back any arc e ? D to T - {f} results in new spanning tree.
Cut optimality conditions: For every tree arc f, and for every non-tree
arc e in its fundamental cut:  c
e
‡ c
f
.
Observation: If c
e
< c
f
then T not a MST.
1
3
8
2
6
7
4
5
f
e
9
10
MST:  Cut Optimality Conditions
Theorem. Cut optimality  MST.   (proof by contradiction)
¦ T = spanning tree that satisfies cut optimality conditions.
T*  = MST that has as many arcs in common with T as possible.
¦ If T = T*, then we are done. Otherwise, let f ? T  s.t.  f ? T*.
¦ Let D be fundamental cut formed by deleting f from T.
¦ Adding f to T* creates a fund cycle C, which shares (at least) two arcs
with cut D. One is f, let e be another. Note:  e  ? T.
¦ Cut optimality conditions   c
f
£ c
e
.
¦ Thus, we can replace e with f in T* without increasing its cost.
f
T T*
e
f
e
11
MST:  Cycle Optimality Conditions
Theorem. Cut optimality  MST.   (proof by contradiction)
¦ T = spanning tree that satisfies cut optimality conditions.
T*  = MST that has as many arcs in common with T as possible.
¦ If T = T*, then we are done. Otherwise, let f ? T  s.t.  f ? T*.
¦ Let D be fundamental cut formed by deleting f from T.
¦ Adding f to T* creates a fund cycle C, which shares (at least) two arcs
with cut D. One is f, let e be another. Note:  e  ? T.
¦ Cut optimality conditions   c
f
£ c
e
.
¦ Thus, we can replace e with f in T* without increasing its cost.
f
T T*
e
f
e
Cycle
cycle
e ? T* s.t. e ? T
Deleting e from cut D
cycle C
C
e f
Cycle f ? T*
12
Towards a Generic MST Algorithm
If all arc weights are distinct:
¦ MST is unique.
¦ Arc with largest weight in cycle C is not in MST.
– cycle optimality conditions
¦ Arc with smallest weight in cutset D is in MST.
– cut optimality conditions
SS’
C
13
Generic MST Algorithm
Red rule.
¦ Let C be a cycle with no red arcs.  Select an uncolored arc of C of
max weight and color it red.
Blue rule.
¦ Let D be a cut with no blue arcs.  Select an uncolored arc in D of
min weight and color it blue.
Greedy algorithm.
¦ Apply the red and blue rules (non-deterministically!) until all arcs
are colored. The blue arcs form a MST.
¦ Note:  can stop once n-1 arcs colored blue.
14
Greedy Algorithm:  Proof of Correctness
Theorem. The greedy algorithm terminates. Blue edges form a MST.
Proof. (by induction on number of iterations)
¦ Base case:  no arcs colored   every MST satisfies invariant.
¦ Induction step:  suppose color invariant true before blue rule.
– let D be chosen cut, and let f be arc colored blue
– if f ? T*, T* still satisfies invariant
– o/w, consider fundamental cycle C by adding f to T*
– let e ? C be another arc in D
– e is uncolored and c
e
‡ c
f
since
! e ? T*   not red
! blue rule  not blue, c
e
‡ c
f
– T* ¨ { f } - { e } satisfies invariant
f
T*
e
Color Invariant:  There exists a MST T* containing all the blue
arcs and none of the red ones.
15
Greedy Algorithm:  Proof of Correctness
Theorem. The greedy algorithm terminates. Blue edges form a MST.
Proof. (by induction on number of iterations)
¦ Base case:  no arcs colored   every MST satisfies invariant.
¦ Induction step:  suppose color invariant true before blue rule.
– let D be chosen cut, and let f be arc colored blue
– if f ? T*, T* still satisfies invariant
– o/w, consider fundamental cycle C by adding f to T*
– let e ? C be another arc in D
– e is uncolored and c
e
‡ c
f
since
! e ? T*   not red
! blue rule  not blue, c
e
‡ c
f
– T* ¨ { f } - { e } satisfies invariant
Color Invariant:  There exists a MST T* containing all the blue
arcs and none of the red ones.
f
e
red
C
cycle
red
e
e  ? T*
cut D deleting e from
f ?DC
f
f  ? T* blue
red rule f not red
T*
16
Greedy Algorithm:  Proof of Correctness
Proof (continued).
¦ Induction step:  suppose color invariant true before red rule.
– cut-and-paste
¦ Either the red or blue rule (or both) applies.
– suppose arc e is left uncolored
– blue edges form a forest
Case 1
e
Case 2
e
Page 5

Princeton University  •  COS 423  •  Theory of Algorithms  •  Spring 2002  •  Kevin Wayne
MST:  Red Rule, Blue Rule
Some of these lecture slides are adapted from material in:
• Data Structures and Algorithms, R. E. Tarjan.
• Randomized Algorithms, R. Motwani and P. Raghavan.
2
Cycles and Cuts
Cycle.
¦ A cycle is a set of arcs of the form {a,b}, {b,c}, {c,d}, . . ., {z,a}.
Cut.
¦ The cut induced by a subset of nodes S is the set of all arcs with
exactly one endpoint in S.
Path = 1-2-3-4-5-6-1
Cycle = {1, 2}, {2, 3}, {3, 4},
{4, 5}, {5, 6}, {6, 1}
1
3
8
2
6
7
4
5
S = {4, 5, 6}
Cut = {5, 6}, {5, 7}, {3, 4},
{3, 5}, {7, 8}
1
3
8
2
6
7
4
5
3
Cycle-Cut Intersection
A cycle and a cut intersect in an even number of arcs.
Proof.
1
3
8
2
6
7
4
5
S
V - S
C
Intersection = {3, 4}, {5, 6}
4
Spanning Tree
Spanning tree.  Let T = (V, F) be a subgraph of G = (V, E).  TFAE:
¦ T is a spanning tree of G.
¦ T is acyclic and connected.
¦ T is connected and has |V| - 1 arcs.
¦ T is acyclic and has |V| - 1 arcs.
¦ T is minimally connected: removal of any arc disconnects it.
¦ T is maximally acyclic: addition of any arc creates a cycle.
¦ T has a unique simple path between every pair of vertices.
1
3
8
2
6
7
4
5
1
3
8
2
6
7
4
5
G = (V, E)
T = (V, F)
5
Minimum Spanning Tree
Minimum spanning tree. Given connected graph G with real-valued
arc weights c
e
, an MST is a spanning tree of G whose sum of arc
weights is minimized.
Cayley’s Theorem (1889). There are n
n-2
spanning trees of K
n
.
¦ n = |V|, m = |E|.
¦ Can’t solve MST by brute force.
1
3
8
2
6
7
4
5
5
23
10
21
14
24
16
6
4
18
9
7
11
8
1
3
8
2
6
7
4
5
5
6
4
9
7
11
8
G = (V, E) T = (V, F)
w(T) = 50
6
Applications
MST is central combinatorial problem with divserse applications.
¦ Designing physical networks.
– telephone, electrical, hydraulic, TV cable, computer, road
¦ Cluster analysis.
– delete long edges leaves connected components
– finding clusters of quasars and Seyfert galaxies
– analyzing fungal spore spatial patterns
¦ Approximate solutions to NP-hard problems.
– metric TSP, Steiner tree
¦ Indirect applications.
– describing arrangements of nuclei in skin cells for cancer research
– learning salient features for real-time face verification
– modeling locality of particle interactions in turbulent fluid flow
– reducing data storage in sequencing amino acids in a protein
7
Optimal Message Passing
Optimal message passing.
¦ Distribute message to N agents.
¦ Each agent can communicate with some of the other agents, but their
communication is (independently) detected with probability p
ij
.
¦ Group leader wants to transmit message (e.g., Divx movie)  to all
agents so as to minimize the total probability that message is detected.
Objective.
¦ Find tree T that minimizes:
¦ Or equivalently, that maximizes:
¦ Or equivalently, that maximizes:
¦ Or equivalently, MST with weights p
ij
.
1- 1- p
ij ( )
(i,j)? T
1- p
ij ( )
(i,j)? T
log 1- p
ij ( )
(i,j)? T
8
Fundamental Cycle
Fundamental cycle.
¦ Adding any non-tree arc e to T forms unique cycle C.
¦ Deleting any arc f ? C from T ¨ {e} results in new spanning tree.
Cycle optimality conditions: For every non-tree arc e, and for every
tree arc f in its fundamental cycle:  c
f
£ c
e
.
Observation: If c
f
> c
e
then T is not a MST.
1
3
8
2
6
7
4
5
f
e
9
9
Fundamental Cut
Fundamental cut.
¦ Deleting any tree arc f from T disconnects tree into two
components with cut D.
¦ Adding back any arc e ? D to T - {f} results in new spanning tree.
Cut optimality conditions: For every tree arc f, and for every non-tree
arc e in its fundamental cut:  c
e
‡ c
f
.
Observation: If c
e
< c
f
then T not a MST.
1
3
8
2
6
7
4
5
f
e
9
10
MST:  Cut Optimality Conditions
Theorem. Cut optimality  MST.   (proof by contradiction)
¦ T = spanning tree that satisfies cut optimality conditions.
T*  = MST that has as many arcs in common with T as possible.
¦ If T = T*, then we are done. Otherwise, let f ? T  s.t.  f ? T*.
¦ Let D be fundamental cut formed by deleting f from T.
¦ Adding f to T* creates a fund cycle C, which shares (at least) two arcs
with cut D. One is f, let e be another. Note:  e  ? T.
¦ Cut optimality conditions   c
f
£ c
e
.
¦ Thus, we can replace e with f in T* without increasing its cost.
f
T T*
e
f
e
11
MST:  Cycle Optimality Conditions
Theorem. Cut optimality  MST.   (proof by contradiction)
¦ T = spanning tree that satisfies cut optimality conditions.
T*  = MST that has as many arcs in common with T as possible.
¦ If T = T*, then we are done. Otherwise, let f ? T  s.t.  f ? T*.
¦ Let D be fundamental cut formed by deleting f from T.
¦ Adding f to T* creates a fund cycle C, which shares (at least) two arcs
with cut D. One is f, let e be another. Note:  e  ? T.
¦ Cut optimality conditions   c
f
£ c
e
.
¦ Thus, we can replace e with f in T* without increasing its cost.
f
T T*
e
f
e
Cycle
cycle
e ? T* s.t. e ? T
Deleting e from cut D
cycle C
C
e f
Cycle f ? T*
12
Towards a Generic MST Algorithm
If all arc weights are distinct:
¦ MST is unique.
¦ Arc with largest weight in cycle C is not in MST.
– cycle optimality conditions
¦ Arc with smallest weight in cutset D is in MST.
– cut optimality conditions
SS’
C
13
Generic MST Algorithm
Red rule.
¦ Let C be a cycle with no red arcs.  Select an uncolored arc of C of
max weight and color it red.
Blue rule.
¦ Let D be a cut with no blue arcs.  Select an uncolored arc in D of
min weight and color it blue.
Greedy algorithm.
¦ Apply the red and blue rules (non-deterministically!) until all arcs
are colored. The blue arcs form a MST.
¦ Note:  can stop once n-1 arcs colored blue.
14
Greedy Algorithm:  Proof of Correctness
Theorem. The greedy algorithm terminates. Blue edges form a MST.
Proof. (by induction on number of iterations)
¦ Base case:  no arcs colored   every MST satisfies invariant.
¦ Induction step:  suppose color invariant true before blue rule.
– let D be chosen cut, and let f be arc colored blue
– if f ? T*, T* still satisfies invariant
– o/w, consider fundamental cycle C by adding f to T*
– let e ? C be another arc in D
– e is uncolored and c
e
‡ c
f
since
! e ? T*   not red
! blue rule  not blue, c
e
‡ c
f
– T* ¨ { f } - { e } satisfies invariant
f
T*
e
Color Invariant:  There exists a MST T* containing all the blue
arcs and none of the red ones.
15
Greedy Algorithm:  Proof of Correctness
Theorem. The greedy algorithm terminates. Blue edges form a MST.
Proof. (by induction on number of iterations)
¦ Base case:  no arcs colored   every MST satisfies invariant.
¦ Induction step:  suppose color invariant true before blue rule.
– let D be chosen cut, and let f be arc colored blue
– if f ? T*, T* still satisfies invariant
– o/w, consider fundamental cycle C by adding f to T*
– let e ? C be another arc in D
– e is uncolored and c
e
‡ c
f
since
! e ? T*   not red
! blue rule  not blue, c
e
‡ c
f
– T* ¨ { f } - { e } satisfies invariant
Color Invariant:  There exists a MST T* containing all the blue
arcs and none of the red ones.
f
e
red
C
cycle
red
e
e  ? T*
cut D deleting e from
f ?DC
f
f  ? T* blue
red rule f not red
T*
16
Greedy Algorithm:  Proof of Correctness
Proof (continued).
¦ Induction step:  suppose color invariant true before red rule.
– cut-and-paste
¦ Either the red or blue rule (or both) applies.
– suppose arc e is left uncolored
– blue edges form a forest
Case 1
e
Case 2
e
17
Special Case:  Prim’s Algorithm
Prim’s algorithm.  (Jarník 1930, Dijkstra 1957, Prim 1959)
¦ S = vertices in tree connected by blue arcs.
¦ Initialize S = any vertex.
¦ Apply blue rule to cut induced by S.
1
3
8
2
6
7
4
5
18
Implementing Prim’s Algorithm
O(m + n log n)
O(n
2
)
Fib. heap
array
Q ‹ PQinit()
for each v ? V
key(v) ‹¥
pred(v) ‹ nil
PQinsert(v, Q)
key(s) ‹ 0
while (!PQisempty(Q))
v = PQdelmin(Q)
for each w ? Q s.t {v,w} ? E
if key(w) > c(v,w)
PQdeckey(w, c(v,w))
pred(w) ‹ v
Prim’s Algorithm
19
Dijkstra’s Shortest Path Algorithm
O(m + n log n)
O(n
2
)
Fib. heap
array
Q ‹ PQinit()
for each v ? V
key(v) ‹¥
pred(v) ‹ nil
PQinsert(v, Q)
key(s) ‹ 0
while (!PQisempty(Q))
v = PQdelmin(Q)
for each w ? Q s.t {v,w} ? E
if key(w) > c(v,w)
PQdeckey(w, c(v,w))
pred(w) ‹ v
Prim’s Algorithm
c(v,w) + key(v)
Dijkstra’s
20
Special Case:  Kruskal’s Algorithm
Kruskal’s algorithm (1956).
¦ Consider arcs in ascending order of weight.
– if both endpoints of e in same blue tree, color red by applying
red rule to unique cycle
– else color e blue by applying blue rule to cut consisting of all
vertices in blue tree of one endpoint
1
3
8
2
6
7
4
5
Case 1: {5, 8}
1
3
8
2
6
7
4
5
Case 2: {5, 6}
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!