Bài giảng Giải thuật - Chương 9: Cây khung nhỏ nhất
Caây Khung Nhoû Nhaát
Caây khung nhoû nhaát
ª Cho
– moät ñoà thò lieân thoâng, voâ höôùng G = (V, E )
– moät haøm troïng soá
w : E → R
ª Tìm moät taäp con khoâng chöùa chu trình T E noái taát caû caùc ñænh sao
cho toång caùc troïng soá
w(T) = (u, v) T w(u, v)
laø nhoû nhaát.
– Taäp T laøø moät caây, vaø ñöôïc goïi laø moät caây khung nhoû nhaát.
ª Baøi toaùn tìm caây khung nhoû nhaát: baøi toaùn tìm T.
13.11.2004
Ch. 9: Cay khung nho nhat
2
Caây khung nhoû nhaát (tieáp)
ª Giaûi baøi toaùn tìm caây khung nhoû nhaát
– Giaûi thuaät cuûa Kruskal
– Giaûi thuaät cuûa Prim.
13.11.2004
Ch. 9: Cay khung nho nhat
3
Caây khung nhoû nhaát: ví duï
8
i
7
b
c
d
f
4
8
2
9
a
e
11
4
14
7
6
10
h
g
1
2
°
°
°
Taäp caùc caïnh xaùm laø moät caây khung nhoû nhaát
Troïng soá toång coäng cuûa caây laø 37.
Caây laø khoâng duy nhaát: neáu thay caïnh (b, c) baèng caïnh (a, h)
seõ ñöôïc moät caây khung khaùc cuõng coù troïng soá laø 37.
13.11.2004
Ch. 9: Cay khung nho nhat
4
Caïnh an toaøn
ª Cho moät ñoà thò lieân thoâng, voâ höôùng G = (V, E ) vaø moät haøm troïng soá
w : E → R. Tìm moät caây khung nhoû nhaát cho G!
ª Giaûi baøi toaùn baèng moät chieán löôïc greedy: nuoâi moät caây khung lôùn
daàn baèng caùch theâm vaøo caây töøng caïnh moät.
ª Ñònh nghóa caïnh an toaøn
Neáu A laø moät taäp con cuûa moät caây khung nhoû nhaát naøo ñoù, neáu (u, v)
laø moät caïnh cuûa G sao cho taäp A {(u, v)} vaãn coøn laø moät taäp con
cuûa moät caây khung nhoû nhaát naøo ñoù, thì (u, v) laø moät caïnh an toaøn
cho A.
13.11.2004
Ch. 9: Cay khung nho nhat
5
Moät giaûi thuaät toång quaùt (generic)
ª Moät giaûi thuaät toång quaùt (generic) ñeå tìm moät caây khung nhoû nhaát
– Input: moät ñoà thò lieân thoâng, voâ höôùng G
moät haøm troïng soá w treân caùc caïnh cuûa G
– Output: Moät caây khung nhoû nhaát cho G.
GENERIC-MST(G, w)
1
2
3
4
5
A
while A khoâng laø moät caây khung nhoû nhaát
do tìm caïnh (u, v) an toaøn cho A
A A {(u, v)}
return A
13.11.2004
Ch. 9: Cay khung nho nhat
6
Pheùp caét
Caùc khaùi nieäm quan troïng
ª Moät pheùp caét (S, V − S) cuûa G = (V, E ) laø moät phaân chia (partition)
cuûa V.
Ví duï: S = {a, b, d, e} trong ñoà thò sau.
ª Moät caïnh (u, v) E xuyeân qua (cross) moät pheùp caét (S, V − S) neáu
moät ñænh cuûa noù naèm trong S vaø ñænh kia naèm trong V − S.
Ví duï: caïnh (b, c).
8
i
7
2
b
c
d
4
8
2
9
a
e
11
4
14
S
7
6
10
h
g
f
V − S
1
13.11.2004
Ch. 9: Cay khung nho nhat
7
Caïnh nheï (light edge)
Caùc khaùi nieäm quan troïng (tieáp)
ª Moät pheùp caét baûo toaøn taäp caùc caïnh A (respects A) neáu khoâng coù
caïnh naøo cuûa A xuyeân qua pheùp caét.
ª Moät caïnh laø moät caïnh nheï vöôït qua pheùp caét neáu troïng soá cuûa noù laø
nhoû nhaát trong moïi troïng soá cuûa caùc caïnh xuyeân qua pheùp caét. Ví duï:
caïnh (c, d).
8
i
7
2
b
c
d
4
8
2
9
a
e
11
4
14
S
7
6
10
h
g
f
V − S
1
13.11.2004
Ch. 9: Cay khung nho nhat
8
Nhaän ra moät caïnh an toaøn
Ñònh lyù 24.1
Cho
°
°
°
°
°
G = (V, E) laø moät ñoà thò lieân thoâng, voâ höôùng
w laø moät haøm troïng soá treân E
A laø moät taäp con cuûa moät caây khung nhoû nhaát cho G
(S, V − S) laø moät pheùp caét baát kyø cuûa G baûo toaøn A
(u, v) laø moät caïnh nheï vöôït qua (S, V − S)
caïnh (u, v) laø an toaøn cho A.
Chöùng minh
13.11.2004
Ch. 9: Cay khung nho nhat
9
Nhaän ra moät caïnh an toaøn
(tieáp)
°
S: taäp caùc ñænh ñen, V − S: taäp caùc ñænh traéng
°
Caùc caïnh cuûa moät caây khung nhoû nhaát T ñöôïc veõ ra trong hình,
coøn caùc caïnh cuûa G thì khoâng
°
°
°
A: taäp caùc caïnh xaùm
Caïnh (u, v) laø caïnh nheï xuyeân qua pheùp caét (S, V − S).
p laø ñöôøng ñi duy nhaát töø u ñeán v trong T.
x
y
u
p
v
13.11.2004
Ch. 9: Cay khung nho nhat
10
Nhaän ra moät caïnh an toaøn
(tieáp)
°
Ñònh nghóa caây khung T’ = T − (x, y) (u, v)
T’ laø caây khung nhoû nhaát vì
w(T’) = w(T) − w(x, y) + w(u, v)
w(T), vì w(u, v) w(x, y)
°
(u, v) laø an toaøn cho A vì A (u, v) T’ .
x
p
y
u
v
13.11.2004
Ch. 9: Cay khung nho nhat
11
Nhaän ra moät caïnh an toaøn (tieáp)
Heä luaän 24.2
Cho
°
°
°
G = (V, E ) laø moät ñoà thò lieân thoâng, voâ höôùng vôùi moät haøm troïng
soá w treân E
A laø moät taäp con cuûa E sao cho A naèm trong moät caây khung nhoû
nhaát cho G
C = (VC , EC ) laø moät thaønh phaàn lieân thoâng (caây) trong röøng GA =
(V, A).
Thì,
neáu (u, v) laø moät caïnh nheï noái C vôùi moät thaønh phaàn khaùc trong GA
(u, v) laø an toaøn cho A.
Chöùng minh
Pheùp caét (VC , V − VC ) baûo toaøn A, do ñoù (u, v) laø moät caïnh nheï ñoái
vôùi pheùp caét naøy.
13.11.2004
Ch. 9: Cay khung nho nhat
12
Giaûi thuaät cuûa Kruskal
ª Giaûi thuaät cuûa Kruskal
– döïa treân giaûi thuaät GENERIC-MST, maø A ban ñaàu laø moät röøng maø
moãi caây chæ chöùa moät ñænh cuûa G.
MST-KRUSKAL(G, w)
1
2
3
4
5
6
7
8
9
A
for moãi ñænh v V[G]
do MAKE-SET(v)
xeáp caùc caïnh E theo thöù töï troïng soá w khoâng giaûm
for moãi caïnh (u, v) E, theo thöù töï troïng soá khoâng giaûm
do if FIND-SET(u) FIND-SET(v)
then A A {(u, v)}
UNION(u, v)
return A
ª moãi taäp rôøi nhau chöùa caùc ñænh cuûa moät caây trong röøng hieän thôøi.
13.11.2004
Ch. 9: Cay khung nho nhat
13
Thöïc thi giaûi thuaät cuûa Kruskal
Caùc caïnh ñöôïc xeáp theo thöù töï troïng soá khoâng giaûm:
1 2 2 4 4 6 7 7 8 8 9 10 11 14
8
i
7
2
8
i
7
2
b
c
d
f
b
c
d
f
(a)
(b)
4
8
2
9
4
8
2
9
a
e
a
e
11
4
14
11
4
14
7
6
7
6
10
10
h
g
h
g
1
1
13.11.2004
Ch. 9: Cay khung nho nhat
14
Thöïc thi giaûi thuaät cuûa Kruskal (tieáp)
1 2 2 4 4 6 7 7 8 8 9 10 11 14
8
i
7
2
8
i
7
2
b
c
d
f
b
c
d
f
(c)
(d)
4
8
2
9
4
8
2
9
a
e
a
e
11
4
14
11
4
14
7
6
7
6
10
10
h
g
h
g
1
1
13.11.2004
Ch. 9: Cay khung nho nhat
15
Thöïc thi giaûi thuaät cuûa Kruskal (tieáp)
8
i
7
8
i
7
2
b
c
d
f
b
c
d
f
(e)
(f)
4
8
2
9
4
8
2
9
a
e
a
e
11
4
14
11
4
14
7
6
7
6
10
10
h
g
h
g
1
2
1
8
7
8
7
b
c
d
b
c
d
(g)
(h)
4
2
9
4
8
2
9
a
i
e
a
i
e
11
4
14
11
4
14
7
6
7
6
8
10
10
h
g
f
h
g
f
1
2
1
2
13.11.2004
Ch. 9: Cay khung nho nhat
16
Thöïc thi giaûi thuaät cuûa Kruskal (tieáp)
8
i
7
8
i
7
2
b
c
d
f
b
c
d
f
(i)
(j)
4
8
2
9
4
8
2
9
a
e
a
e
11
4
14
11
4
14
7
6
7
6
10
10
h
g
h
g
1
2
1
8
7
8
7
b
c
d
b
c
d
(k)
(l)
4
8
2
9
4
2
9
a
i
e
a
i
e
11
4
14
11
4
14
7
6
7
6
10
8
10
h
g
f
h
g
f
1
2
1
2
13.11.2004
Ch. 9: Cay khung nho nhat
17
Thöïc thi giaûi thuaät cuûa Kruskal (tieáp)
1 2 2 4 4 6 7 7 8 8 9 10 11 14
8
i
7
2
8
i
7
2
b
c
d
f
b
c
d
f
(m)
(n)
4
8
2
9
4
8
2
9
a
e
a
e
11
4
14
11
4
14
7
6
7
6
10
10
h
g
h
g
1
1
13.11.2004
Ch. 9: Cay khung nho nhat
18
Phaân tích giaûi thuaät cuûa Kruskal
ª Duøng caáu truùc döõ lieäu caùc taäp rôøi nhau (disjoint sets), chöông 22, vôùi
caùc heuristics
– Hôïp theo thöù haïng (union-by-rank)
– Neùn ñöôøng daãn (path-compression).
ª Nhaän xeùt (caàn ñeán khi ñaùnh giaù thôøi gian chaïy)
– Giaûi thuaät goïi V laàn MAKE-SET vaø goïi toång coäng O(E) laàn caùc
thao taùc MAKE-SET, UNION, FIND-SET.
– Vì G lieân thoâng neân |E| |V| − 1.
13.11.2004
Ch. 9: Cay khung nho nhat
19
Phaân tích giaûi thuaät cuûa Kruskal (tieáp)
ª Thôøi gian chaïy cuûa MST-KRUSKAL goàm
– Khôûi ñoäng: O(V)
– Saép xeáp ôû doøng 4: O(E lg E)
– Doøng 5-8: O(E (E, V)) (xem nhaän xeùt),
= O(E lg E) vì (E, V) = O(lg E).
Vaäy thôøi gian chaïy cuûa MST-KRUSKAL laø O(E lg E).
13.11.2004
Ch. 9: Cay khung nho nhat
20
Tải về để xem bản đầy đủ
29 trang
27/04/2022
3440
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Giải thuật - Chương 9: Cây khung nhỏ nhất", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_giai_thuat_chuong_9_cay_khung_nho_nhat.ppt
