Cây Khung Nh Nh tỏ ấ
13.11.2004 Ch. 9: Cay khung nho nhat 2
Cây khung nh nh tỏ ấ
ªCho
–m t đ th liên thông, vô h ng ộ ồ ị ướ G = (V, E )
–m t ộhàm tr ng sọ ố
w : E R
ªTìm m t t p con ộ ậ không ch a chu trìnhứ T E n i t t c các đnh sao ố ấ ả ỉ
cho t ng các tr ng s ổ ọ ố
w(T) = (u, v) T w(u, v)
•là nh nh t.ỏ ấ
–T p ậT làø m t cây, và đc g i là m t ộ ượ ọ ộ cây khung nh nh tỏ ấ .
ª Bài toán tìm cây khung nh nh tỏ ấ : bài toán tìm T.
13.11.2004 Ch. 9: Cay khung nho nhat 3
Cây khung nh nh t (ti p)ỏ ấ ế
ªGi i bài toán tìm cây khung nh nh tả ỏ ấ
–Gi i thu t c a Kruskalả ậ ủ
–Gi i thu t c a Prim.ả ậ ủ
13.11.2004 Ch. 9: Cay khung nho nhat 4
Cây khung nh nh t: ví d ỏ ấ ụ
b
f
c d
h g
ia e
8 7
9
10
1 2
4
14
2
4
7 6
11
8
° T p các c nh xám là m t cây khung nh nh tậ ạ ộ ỏ ấ
° Tr ng s t ng c ng c a cây là 37.ọ ố ổ ộ ủ
° Cây là không duy nh t: n u thay c nh (ấ ế ạ b, c) b ng c nh (ằ ạ a, h)
s đc m t cây khung khác cũng có tr ng s là 37.ẽ ượ ộ ọ ố
13.11.2004 Ch. 9: Cay khung nho nhat 5
C nh an toànạ
ªCho m t đ th liên thông, vô h ng ộ ồ ị ướ G = (V, E ) và m t hàm tr ng s ộ ọ ố
w : E R. Tìm m t cây khung nh nh t cho ộ ỏ ấ G!
ªGi i bài toán b ng m t ả ằ ộ chi n l c greedyế ượ : nuôi m t cây khung l n ộ ớ
d n b ng cách thêm vào cây t ng c nh m t.ầ ằ ừ ạ ộ
ªĐnh nghĩaị c nh an toànạ
N u ếA là m t t p con c a m t cây khung nh nh t nào đó, n u (ộ ậ ủ ộ ỏ ấ ế u, v)
là m t c nh c a ộ ạ ủ G sao cho t p ậA {(u, v)} v n còn là m t t p con ẫ ộ ậ
c a m t cây khung nh nh t nào đó, thì (ủ ộ ỏ ấ u, v) là m t ộc nh an toànạ
cho A.