...

4. G II Red-rule blue-rule demo

by user

on
Category: Documents
1

views

Report

Comments

Transcript

4. G II Red-rule blue-rule demo
4. G REEDY ALGORITHMS II
‣ Red-rule blue-rule demo
Lecture slides by Kevin Wayne
Copyright © 2005 Pearson-Addison Wesley
Copyright © 2013 Kevin Wayne
http://www.cs.princeton.edu/~wayne/kleinberg-tardos
Last updated on Sep 8, 2013 6:20 AM
Red-rule blue-rule demo
Red rule. Let C be a cycle with no red edges. Select an uncolored edge of C
of max weight and color it red.
Blue rule. Let D be a cutset with no blue edges. Select an uncolored edge in
D of min weight and color it blue.
the input graph
9
1
5
3
2
7
6
4
8
2
Red-rule blue-rule demo
Red rule. Let C be a cycle with no red edges. Select an uncolored edge of C
of max weight and color it red.
apply the red rule to the cycle
9
2
4
3
8
3
Red-rule blue-rule demo
current set of red and blue edges
4
Red-rule blue-rule demo
Red rule. Let C be a cycle with no red edges. Select an uncolored edge of C
of max weight and color it red.
apply the red rule to the cycle
2
7
4
8
5
Red-rule blue-rule demo
Red rule. Let C be a cycle with no red edges. Select an uncolored edge of C
of max weight and color it red.
current set of red and blue edges
6
Red-rule blue-rule demo
Blue rule. Let D be a cutset with no blue edges. Select an uncolored edge in
D of min weight and color it blue.
apply the blue rule to the cutset
1
5
7
6
4
7
Red-rule blue-rule demo
current set of red and blue edges
8
Red-rule blue-rule demo
Blue rule. Let D be a cutset with no blue edges. Select an uncolored edge in
D of min weight and color it blue.
apply the blue rule to the cutset
9
5
3
9
Red-rule blue-rule demo
current set of red and blue edges
10
Red-rule blue-rule demo
apply the red rule to the cycle
2
6
4
11
Red-rule blue-rule demo
current set of red and blue edges
12
Red-rule blue-rule demo
Blue rule. Let D be a cutset with no blue edges. Select an uncolored edge in
D of min weight and color it blue.
apply the blue rule to the cutset
9
2
7
4
8
13
Red-rule blue-rule demo
current set of red and blue edges
14
Red-rule blue-rule demo
Blue rule. Let D be a cutset with no blue edges. Select an uncolored edge in
D of min weight and color it blue.
apply the blue rule to the cutset
6
4
8
15
Red-rule blue-rule demo
current set of red and blue edges
16
Red-rule blue-rule demo
Blue rule. Let D be a cutset with no blue edges. Select an uncolored edge in
D of min weight and color it blue.
apply the blue rule to the cutset
9
7
8
17
Red-rule blue-rule demo
current set of red and blue edges
18
Red-rule blue-rule demo
Blue rule. Let D be a cutset with no blue edges. Select an uncolored edge in
D of min weight and color it blue.
apply the red rule to the cycle
1
5
3
19
Red-rule blue-rule demo
current set of red and blue edges
20
Red-rule blue-rule demo
Greedy algorithm. Upon termination, the blue edges form a MST.
a minimum spanning tree
2
1
7
4
3
21
Fly UP