1
30/10/2012 1
Toán rời rạc (6):
CÂY VÀ MỘT SỐ ỨNG
DỤNG CỦA CÂY
Ts. Hoàng ThịThanh Hà
Khoa Thống kê –Tin học
Trường Đại học Kinh tế
30/10/2012 2
NỘI DUNG
1. Khái niệm cây
2. Cây bao trùm
3. Cây bao trùm nhỏnhất
4. Cây bao trùm lớn nhất
5. Cây phân cấp
6. Duyệt cây
7. Cây nhịphân
1. Cây biểu thức
2. Cây mã tiền tố
30/10/2012 3
1. KHÁI NIỆM CÂY
Khái niệm cây do Cayley đưa ra vào năm 1857.
Định nghĩa 1:GiảsửT = (V, E) là mộtđồ thịvô
hướng. T là mộtcây nếu nó thỏa mãn hai tính chất
sau:
- liên thông,
- không có chu trình.
Cây không có chu trình nên không có khuyên, không
có cạnh bội, nên ta quy ướcĐồ thịvô hướng chính là
đơnđồ vo hướng
Mộtđồ thịvô hướng không chứa chu trình và có ít
nhất hai đỉnh gọi là một rừng. Trong một rừng, mỗi
thành phần liên thông là một cây.
30/10/2012 4
1. VÍ DỤ 1
Ví dụ:Rừng sau có 3 cây:
a
b
cf
d
e
g h j
i
k
l
m
n
30/10/2012 5
1. KHÁI NIỆM CÂY (tiếp)
Định lý 1:Cho T là đồ thịvô hướng có số đỉnh không
ít hơn 2. Khi đó các khẳng định sau là tương đương:
1) T là một cây.
2) T liên thông và có n−1 cạnh.
3) T không chứa chu trình và có n−1 cạnh.
4) T liên thông và mỗi cạnh là cầu.
5) Giữa hai đỉnh phân biệt bất kỳcủa T luôn có duy
nhất mộtđường đi sơcấp.
6) T không chứa chu trình nhưng khi thêm một cạnh
mới thì có được một chu trình duy nhất.
30/10/2012 6
1. KHÁI NIỆM CÂY (tiếp)
Chứng minh: 1)⇒
⇒⇒
⇒2) Chỉcần chứng minh rằng
một cây có n đỉnh thì có n−1 cạnh. Ta chứng
minh bằng quy nạp. Điều này hiển nhiên khi
n=2. Giảsửcây có k đỉnh thì có k−1 cạnh, ta
chứng minh rằng cây T có k+1 đỉnh thì có k
cạnh. Thật vậy, trong T nếu ta xoá mộtđỉnh
treo và cạnh treo tương ứng thì đồ thịnhận
được là một cây k đỉnh, cây này có k−1 cạnh,
theo giảthiết quy nạp. Vậy cây T có k cạnh.
2
30/10/2012 7
1. KHÁI NIỆM CÂY (tiếp)
Chứng minh:2)⇒
⇒⇒
⇒3) Nếu T có chu trình thì bỏ đi một cạnh
trong chu trình này thì T vẫn liên thông. Làm lại như
thếcho đến khi trong T không còn chu trình nào mà
vẫn liên thông, lúc đó ta được một cây có n đỉnh
nhưng có ít hơn n−1 cạnh, trái với 2).
3)⇒
⇒⇒
⇒4) Nếu T có k thành phần liên thông T1, ..., Tk
lần lượt có số đỉnh là n1, ..., nk (với n1+n2+ …
+nk=n) thì mỗi Ti là một cây nên nó có sốcạnh là
ni−1. Vậy ta có: n−1=(n1−1)+(n2−1)+ ...
+(nk−1)=(n1+n2+ …+nk)−k=n−k.
Do đó k=1 hay T liên thông. Hơn nữa, khi bỏ đi một
cạnh thì T hết liên thông, vì nếu còn liên thông thì T
là một cây n đỉnh với n−2 cạnh, trái vớiđiềuđã chứng
minh ởtrên.
30/10/2012 8
1. KHÁI NIỆM CÂY (tiếp)
Chứng minh:4)⇒
⇒⇒
⇒5) Vì T liên thông nên giữa hai đỉnh
phân biệt bất kỳcủa T luôn có mộtđường đi sơcấp,
nhưng không thể được nối bởi hai đường đi sơcấp vì
nếu thế, hai đường đó sẽtạo ra một chu trình và khi
bỏmột cạnh thuộc chu trình này, T vẫn liên thông,
trái với giảthiết.
5)⇒
⇒⇒
⇒6) Nếu T chứa một chu trình thì hai đỉnh bất kỳ
trên chu trình này sẽ được nối bởi hai đường đi sơ
cấp. Ngoài ra, khi thêm một cạnh mới (u,v), cạnh này
sẽtạo nên vớiđường đi sơcấp duy nhất nối u và v
một chu trình duy nhất.
6)⇒
⇒⇒
⇒1) Nếu T không liên thông thì thêm một cạnh nối
hai đỉnh ởhai thành phần liên thông khác nhau ta
không nhậnđược một chu trình nào. Vậy T liên
thông, do đó nó là một cây.
30/10/2012 9
2. CÂY BAO TRÙM
Định nghĩa 2
GiảsửG là mộtđồ thịvô hướng liên thông.
Nếu ta loại bỏcạnh nằm trên chu trình nào đó
thì ta sẽ đượcđồ thịvẫn là liên thông. Nếu cứ
loại bỏcác cạnh ởcác chu trình khác cho đến
khi nào đồ thịkhông còn chu trình (vẫn liên
thông) thì ta thu được một cây nối các đỉnh
của G. Cây đó gọi là cây khung hay cây bao
trùm củađồ thịG.
Hay cho đồ thịG, đồ thịcon T chứa tất cảcác
đỉnh, T là 1 cây => T là cây bao trùm của G
30/10/2012 10
2. VÍ DỤ CÂY BAO TRÙM
Đồ thịG có cây bao trùm:
a
d
b
e
c
a
d
b
e
c
a
d
b
e
c
Hai cây bao trùm của đồ thị G
30/10/2012 11
2. CÂY BAO TRÙM (tiếp)
Định lý 2:Đồ thịvô hướng G có cây bao trùm ⇔G
liên thông.
Chứng minh:
⇒Hiển nhiên, vì cây bao trùm liên thông suy ra G
liên thông.
⇐Chọnalà mộtđỉnh bất kỳtrong đồ thịG.
Ký hiệu: d(x) là khoảng cách giữaavà đỉnh x.
Xây dựng các tậpđỉnh:
D0= {a}, Di= { xd(x) = i } vớii≥1.
30/10/2012 12
2. CÂY BAO TRÙM (tiếp)
a
D0D1D2. . .
Cách xây dựng cây bao trùm
Chú ý: Mỗi đỉnh xthuộc Di(i≥1) đều có đỉnh ythuộc Di-1 sao
cho (x, y) là một cạnh, vì nếu < a, ... , y, x > là đường đi ngắn nhất
nối avới xthì < a, ... , y > là đường đi ngắn nhất nối avới y
và y ∈Di-1.
3
30/10/2012 13
2. CÂY BAO TRÙM (tiếp)
Chứng minh (tiếp): Lập tập cạnh T nhưsau:
Với mỗiđỉnh xcủađồ thịG, x∈Divớii≥1, ta lấy
cạnh nào đó nốixvới mộtđỉnh trong Di-1.
Tập cạnh này sẽtạo nên mộtđồ thịriêng của G vớin
đỉnh và n- 1 cạnh.
Đồ thịriêng này liên thông vì mỗiđỉnh đềuđược nối
vớiđỉnh a. Theo tính chất 2) của cây thì T là một cây.
Do vậy, T là cây bao trùm củađồ thịG.
30/10/2012 14
3. CÂY BAO TRÙM NHỎ NHẤT
Bài toán: Cho đồ thịvô hướng G liên thông với
tập cạnh Evà hàm trọng sốc:E→N. Tìm cây
bao trùm T của G sao cho tổng trọng sốcủa các
cạnh của T đạt giá trịnhỏnhất.
Một sốthuật toán tìm cây bao trùm nhỏnhất:
- Thuật toán Kruskal
- Thuật toán Prim
30/10/2012 15
3.1. THUẬT TOÁN KRUSKAL
Thuật toán:
Đầu vào: Đồ thịG và ma trận trọng sốM
Đầu ra: Độ lớn của cây khung và tô đậm cây khung
1. Sắp xếp các cạnh tăng dần theo trọng số. Chọn
ecó trọng sốbé nhất, giảsửe1,đặt W= {e1}.
2. Giảsử đã chọnđược W = {e1, e2, ... , ei}. Chọn
ei+1 là cạnh có trọng sốbé nhất trong sốcác
cạnh còn lại trong E\ W sao cho {e1, e2, ... , ei,
ei+1} không chứa chu trình.
3. Bổsung: W := W ∪{ei+1}.
4. Lặp lại các bước 2, 3 chừng nào còn có thể.
30/10/2012 16
3.1. THUẬT TOÁN KRUSKAL
Đồ thịcó trọng sốvà cây bao trùm nhỏnhất:
1
1
1
2
2
4
6
5 6 5
11
1
2
2
4
6
5 6 5
30/10/2012 17
3.1. THUẬT TOÁN KRUSKAL
Đồ thịcó trọng sốvà cây bao trùm nhỏnhất:
33
17
18 16
4
9
8
14
20
33
17
18 16
4
9
8
14
20
30/10/2012 18
3.1. THUẬT TOÁN KRUSKAL (tiếp)
Định lý 3 : Tập các cạnh W tìm được
theo thuật toán Kruskal tạo nên cây bao
trùm nhỏnhất củađồ thịG.
Thuật toán Kruskal chi tiết
1 procedure Kruskal ;
2 begin
3 W := ∅; Z := E ;
4
30/10/2012 19
3.1. THUẬT TOÁN KRUSKAL (tiếp)
4 while (|W| < n-1) and (Z ≠ ∅) do
5 begin
6chọn cạnh e có trọng sốbé nhất trong Z ;
7 Z := Z \ {e} ;
8 if W ∪{e}không chứa chu trình then
W := W ∪{e}
9 end ;
10 if |W| < n-1 then writeln(″Đồ thịkhông liên
thông″)
11 end ;
30/10/2012 20
3.2. THUẬT TOÁN PRIM
Nhận xét: Thuật toán Kruskal làm việc kém
hiệu quả đối với những đồ thịdày (đồ thịcó số
cạnh m ≈n(n−1)/2). Trong trường hợpđó,
thuật toán Prim tỏra hiệu quảhơn. Thuật toán
Prim còn được gọi là phương pháp lân cận gần
nhất.
Thuật toán Prim
Prim đã cải tiến thuật toán Kruskal nhưsau:
ởmỗi vòng lặp ta chọn cạnh có trọng sốbé
nhất trong sốcác cạnh kềvới các cạnh đã
chọn mà không tạo nên chu trình.
30/10/2012 21
3.2. THUẬT TOÁN PRIM (tiếp)
Thuật toán Prim: bắtđầu từmộtđỉnh anào đó
củađồ thịG ta nối nó vớiđỉnh “gần” nhất,
chẳng hạnb. Nghĩa là, cạnh (a, b)được chọn
có trọng sốbé nhất. Tiếp theo, trong sốcác
cạnh kềvớiđỉnh ahoặcđỉnh bta chọn cạnh
có trọng sốbé nhất mà không tạo nên chu
trình với cạnh (a, b). Cạnh này dẫnđếnđỉnh
thứba c...
Tiếp tục quá trình này cho đến khi nhậnđược
cây gồmnđỉnh và n-1 cạnh. Đó chính là
cây bao trùm nhỏnhất.
30/10/2012 22
3.2. THUẬT TOÁN PRIM (tiếp)
1 procedure Prim ;
2 begin
3 W := {cạnh có trọng sốbé nhất};
4 for i:= 1 to n- 2 do
5 begin
6e:= cạnh có trọng sốbé nhất kềvới cạnh
trong W và nếu ghép nó vào W thì không
tạo nên chu trình ;
7W := W ∪{e}
8 end
9 end ;
30/10/2012 23
4. CÂY BAO TRÙM LỚN NHẤT
Trong các thuật toán Kruskal và Prim ta
không ràng buộc vềdấu của trọng số, nên có
thểáp dụng cho đồ thịvô hướng với trọng số
trên các cạnh có cùng dấu tuỳý.
30/10/2012 24
4. CÂY BAO TRÙM LỚN NHẤT (tiếp)
Để tìm cây bao trùm lớn nhất ta có hai cách:
1. Đổi thành dấu - cho các trọng sốtrên các cạnh. áp
dụng một trong hai thuật toán đã trình bày ởtrên
để tìm cây bao trùm nhỏnhất. Sau đóđổi dấu +
trởlại, ta sẽ được cây bao trùm lớn nhất.
2. Sửađổi trong các thuật toán: bước “chọn cạnh có
trọng sốbé nhất ... “được thay bằng “chọn cạnh
có trọng sốlớn nhất ... “ còn các bước khác thì
giữnguyên. Khi thuật toán kết thúc, ta sẽnhận
được cây bao trùm lớn nhất.
5
30/10/2012 25
5. CÂY PHÂN CẤP
Định nghĩa 4:Cây phân cấp là một cây, trong đó có
mộtđỉnh đặc biệt gọi là gốc, giữa các đỉnh có mối
quan hệphân cấp “cha-con”.
Một sốthuật ngữ:
- Sốcác con của mộtđỉnh trong cây phân cấp
được gọi là bậccủađỉnh đó.
-Đỉnh không có con được gọi là lá của cây.
-Đỉnh không phải là lá được gọi là đỉnh trong của
cây, còn lá được gọi là đỉnh ngoài của cây. Đỉnh
gốc là đỉnh duy nhất không có cha.
30/10/2012 26
5. CÂY PHÂN CẤP (tiếp)
-Mứccủađỉnh trong cây phân cấp:
Gốc của cây có mức là 0.
Nếu mức củađỉnh cha là ithì mức của các
đỉnh con là i+ 1.
- Chiều cao của cây là mức cao nhất của các đỉnh
trong cây.
30/10/2012 27
5. VÍ DỤ
Cây T dướiđây có đỉnh gốca, các đỉnh lá b, g, e,
h, k.
a
bc
de f
g h k
Hình Cây phân cấp
30/10/2012 28
5. CÂY PHÂN CẤP (tiếp)
Định nghĩa 5 (đệ quy)
- Tập rỗng là một cây phân cấp (cây rỗng).
- Mộtđỉnh là một cây phân cấp.
- Giảsửalà mộtđỉnh và T1, T2, ... , Tklà các cây
phân cấp với các gốc là a1, a2, ..., aktương ứng.
Cây T được xây dựng bằng cách cho đỉnh alàm
“cha” của các đỉnh a1, a2, ..., ak,sẽlà một cây
phân cấp. Trong cây T này, đỉnh a là gốc và T1,
T2, ... , Tklà các cây con của gốca.
30/10/2012 29
5. CÂY PHÂN CẤP (tiếp)
Đường đi trong cây phân cấp T là một dãy các đỉnh
<b1, b2, ..., bm> mà:
bilà “cha” củabi + 1, 1 ≤i≤m-1.
Cây phân cấp T với bậc cao nhất của các đỉnh trong
T là m,được gọi là cây m- phân.
Cây m-phân đầyđủ là cây mà mọiđỉnh trong có
đúng m con.
a
a1a2ak
T1T2Tk
. . .
Hình 12. Cây phân cấp tổng quát
30/10/2012 30
5. CÂY PHÂN CẤP (tiếp)
Định lý 4
GiảsửT là một cây m-phân.
- Nếu cây T có chiều cao hthì cây có nhiều nhấtmh
lá.
- Nếu cây T có llá thì cây có chiều cao h≥[logml].