Cây Nguyễn Thế Vinh- ĐHKH
108
nhỏ đến cạnh có độ dài lớn hơn, để tìm ra cạnh mà việc bổ sung nó vào tập E
T
không tạo thành chu trình trong tập này. Thuật toán sẽ kết thúc khi ta thu được
tập E
T
gồm n−1 cạnh. Cụ thể có thể mô tả như sau:
Bước 1: Bắt đầu từ đồ thị rỗng T có n đỉnh.
Bước 2: Sắp xếp các cạnh của G theo thứ tự không giảm của trọng số.
Bước 3: Bắt đầu từ cạnh đầu tiên của dãy này, ta cứ thêm dần các cạnh
của dãy đã được xếp vào T theo nguyên tắc cạnh thêm vào không được tạo
thành chu trình trong T.
Bước 4: Lặp lại Bước 3 cho đến khi nào số cạnh trong T bằng n−1, ta
thu được cây khung nhỏ nhất cần tìm.
Ví dụ: Tìm cây khung nhỏ nhất của đồ thị cho trong hình dưới đây:
Bắt đầu từ đồ thị rỗng T có 6 đỉnh.
Sắp xếp các cạnh của đồ thị theo thứ tự không giảm của trọng số:
{(v
3
, v
5
), (v
4
, v
6
), (v
4
, v
5
), (v
5
, v
6
), (v
3
, v
4
), (v
1
, v
3
), (v
2
, v
3
), (v
2
, v
4
), (v
1
, v
2
)}.
Thêm vào đồ thị T cạnh (v
3
, v
5
).
Do số cạnh của T là 1<6−1 nên tiếp tục thêm cạnh (v
4
, v
6
) vào T. Bây
giờ số cạnh của T đã là 2 vẫn còn nhỏ hơn 6, ta tiếp tục thêm cạnh tiếp theo
trong dãy đã sắp xếp vào T. Sau khi thêm cạnh (v
4
, v
5
) vào T, nếu thêm cạnh
(v
5
, v
6
) thì nó sẽ tạo thành với 2 cạnh (v
4
, v
5
), (v
4
, v
6
) đã có trong T một chu
trình. Tình huống tương tự cũng xãy ra đối với cạnh (v
3
, v
4
) là cạnh tiếp theo
trong dãy. Tiếp theo ta bổ sung cạnh (v
1
, v
3
), (v
2
, v
3
) vào T và thu dược tập E
T
gồm 5 cạnh:
{(v
3
, v
5
), (v
4
, v
6
), (v
4
, v
5
), (v
1
, v
3
), (v
2
, v
3
)}.
Tính đúng đắn của thuật toán: Rõ ràng đồ thị thu được theo thuật
toán có n−1 cạnh và không có chu trình. Vì vậy theo Định lí 6.1.3, nó là cây
khung của đồ thị G. Như vậy chỉ còn phải chỉ ra rằng T có độ dài nhỏ nhất.
v
1
v
2
v
3
v
4
v
5
v
6
v
2
v
3
v
1
v
4
v
5
v
6
33
17
18
16
4
9
8
14
20
Cây Nguyễn Thế Vinh- ĐHKH
109
Giả sử tồn tại cây khung S của đồ thị mà m(S)<m(T). Ký hiệu e
k
là cạnh đầu
tiên trong dãy các cạnh của T xây dựng theo thuật toán vừa mô tả không thuộc
S. Khi đó đồ thị con của G sinh bởi cây S được bổ sung cạnh e
k
sẽ chứa một
chu trình duy nhất C đi qua e
k
. Do chu trình C phải chứa cạnh e thuộc S nhưng
không thuộc T nên đồ thị con thu được từ S bằng cách thay cạnh e của nó bởi
e
k
, ký hiệu đồ thị này là S’, sẽ là cây khung. Theo cách xây dựng, m(e
k
)≤m(e),
do đó m(S’)≤m(S), đồng thời số cạnh chung của S’ và T đã tăng thêm một so
với số cạnh chung của S và T. Lặp lại quá trình trên từng bước một, ta có thể
biến đổi S thành T và trong mỗi bước tổng độ dài không tăng, tức là
m(T)≤m(S). Mâu thuẩn này chứng tỏ T là cây khung nhỏ nhất của G.
Độ phức tạp của thuật toán Kruskal được đánh giá như sau. Trước tiên,
ta sắp xếp các cạnh của G theo thứ tự có chiều dài tăng dần; việc sắp xếp này
có độ phức tạp O(p
2
), với p là số cạnh của G. Người ta chứng minh được rằng
việc chọn e
i+1
không tạo nên chu trình với i cạnh đã chọn trước đó có độ phức
tạp là O(n
2
). Do p≤n(n−1)/2, thuật toán
Kruskal có độ phức tạp là O(p
2
).
Khi cài đặt thuật toán Kruskal có hai vấn đề phải giải quyết
Vấn đề thứ nhất: làm thế nào để xét được các cạnh có trọng số từ nhỏ
đến lớn vấn đề này ta có thể thực hiện bằng thuật toán sắp xếp danh sách cạnh
theo thứ tự tăng dần. Trong trường hợp tổng quát ta sử dụng thuật toán
Heapsort là hiệu quả nhất bởi nó cho phép chọn lần lượt các cạnh từ trọng số
nhỏ nhất tới trọng số lớn nhất ra khỏi Heap.
Vấn đề thứ hai: làm thế nào kiểm tra xem việc thêm một cạnh có tạo
thành chu trình đơn trong cây khung hay không?. Ta nhận thấy rằng các cạnh
trong cây khung ở các bước sẽ tạo thành rừng T, vì vậy muốn thêm một cạnh
(u,v) vào cây khung mà không tạo thành chu trình thì (u,v) phải nối hai cây
khác nhau của rừng T. Ban đầu ta khởi tạo rừng T gồm n cây, mỗi cây chỉ
đúng một đỉnh sau đó mỗi khi xét đến cạnh nối hai cây khác nhau của rừng T
thì ta kết nạp cạnh đó vào T, đồng thời hợp nhất hai cây đó thành một cây.
Cây Nguyễn Thế Vinh- ĐHKH
110
Để làm điều này ta gán cho mỗi đỉnh v một nhãn Lab[v] là số hiệu đỉnh
cha của đỉnh v trên cây (nếu v là gốc gán giá trị 0). Tạo hàm Getroot(v) để xác
định được gốc của cây chứa đỉnh v.
Function Getroot(v:Item): Item;
Begin
while (Lab[v]>0) do v:=Lab[v];
Getroot(v):=v;
End;
Cuối cùng để kiểm tra cạnh (u,v) có nối hai cây khác nhau của rừng T
hay không ta kiểm tra Getroot(u) có khác Getroot(v) hay không. Để hợp nhất
cây gốc r1 và cây gốc r2 ta chỉ việc coi r1 là nút cha của r2 trong cây bằng
cách gán Lab[r2]=r1 (thông thường chọn cây nhiều nút hơn làm cha).
5.2.4. Thuật toán Prim: 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.
Bước 1: V
T
:={v
*
}, trong đó v
*
là đỉnh tuỳ ý của đồ thị G.
E
T
:=Φ
Bước 2: Với mỗi đỉnh v
j
∉V
T
, tìm đỉnh w
j
∈V
T
sao cho
m(w
j
,v
j
) = min m(x
i
, v
j
)=:β
j
x
i
∈V
T
và gán cho đỉnh v
j
nhãn [w
j
, β
j
]. Nếu không tìm đuợc w
j
như vậy (tức là
khi v
j
không kề với bất cứ đỉnh nào trong V
T
) thì gán cho v
j
nhãn [0, ∞].
Bước 3: Chọn đỉnh v
j*
sao cho
β
j*
= min β
j
v
j
∉V
T
V
T
:= V
T
∪ {v
j*
},
E
T
:= E
T
∪ {(w
j*
, v
j*
)}.
Nếu |V
T
| = n thì thuật toán dừng và (V
T
, E
T
) là cây khung nhỏ nhất.
Nếu |V
T
| < n thì chuyển sang Bước 4.
Cây Nguyễn Thế Vinh- ĐHKH
111
Bước 4: Đối với tất cả các đỉnh v
j
∉V
T
mà kề với v
j*
, ta thay đổi nhãn
của chúng như sau:
Nếu β
j
> m(v
j*
, v
j
) thì đặt β
j
:=m(v
j*
, v
j
) và nhãn của v
j
là [v
j*
, β
j
]. Ngược
lại, ta giữ nguyên nhãn của v
j
. Sau đó quay lại Bước 3.
Ví dụ: Tìm cây khung nhỏ nhất bằng thuật toán Prim của đồ thị gồm
các đỉnh sau.
Yêu cầu viết các kết quả trung gian trong từng bước lặp, kết quả cuối
cùng cần đưa ra tập cạnh và độ dài của cây khung nhỏ nhất.
V.lặp
A B C D E F
V
T
E
T
K.tạo - [33,A] [17,A]*
[∞,A] [∞,A] [∞,A]
A
∅
1 - [18,C] - [16,C] [4,C]*
[∞,A]
A,C (A,C)
2 - [18,C] - [9,E]* - [14,E] A,C,E (A,C) (C,E)
3 - [18,C] - - - [8,D]* A,C,E,D (A,C) (C,E) (E,D)
4 - [18,C]* - - - - A,C,E,
D,F
(A,C) (C,E) (E,D)
(D,F)
5 - - - - - - A,C,E,
D,F,B
(A,C) (C,E) (E,D)
(D,F) (C,B)
Vậy độ dài cây khung nhỏ nhất là: 17 + 4 + 9 + 8 + 18 = 56.
Tính đúng đắn của thuật toán: Để chứng minh thuật toán Prim là
đúng, ta chứng minh bằng quy nạp rằng T(k) (k=1, 2, ,n), đồ thị nhận được
trong vòng lặp thứ k, là một đồ thị con của cây khung nhỏ nhất của G, do đó
T(n) chính là một cây khung nhỏ nhất của G.
T(1) chỉ gồm đỉnh v
*
của G, do đó T(1) là đồ thị con của mọi cây khung
của G. Giả sử T(i) (1≤i<n) là một đồ thị con của một cây khung nhỏ nhất của
G. Ta chứng minh rằng T(i+1) cũng là đồ thị con của một cây khung nhỏ nhất.
Thật vậy, theo thuật toán Prim E
T(i+1)
=E
T(i)
∪ {e
i+1
}, với e
i+1
là cạnh
ngắn nhất trong tất cả các cạnh có một đầu mút thuộc V
T(i)
, đầu mút kia không
thuộc V
T(i)
.
B
C
A
D
E
F
33
17
18
16
4
9
8
14
20
Cây Nguyễn Thế Vinh- ĐHKH
112
Nếu e
i+1
là một cạnh của T thì T
i+1
là đồ thị con của T.
Nếu e
i+1
không phải là một cạnh của T thì T
i+1
là đồ thị con T’=(V
T
,
E
T
∪{e
i+1
}). Đồ thị T’ chứa một chu trình sơ cấp duy nhất C (theo tính chất 6
của định lí về cây). Ta chọn trong C một cạnh e
j
có một đỉnh thuộc T(i) và
đỉnh kia không thuộc T(i) và e
j
≠e
i+1
. Ta bỏ e
j
trong C.
Khi đó T’’=(V
T
, E
T’
\ {e
j
}) là một cây khung của G và T(i+1) là đồ thị
con của T’ nên cũng là đồ thị con của T’’. Theo cách chọn e
i+1
của thuật toán
Prim, ta có m(e
i+1
) ≤ m(e
j
) do đó m(T’’) ≤ m(T).
Nhưng T’’ là một cây khung của G, còn T là cây khung nhỏ nhất, vì vậy
phải có m(T’’)=m(T), tức là T’’ cũng là cây khung nhỏ nhất của G.
Độ phức tạp của thuật toán Prim là O(n
3
). Thật vậy, nếu T(k) có k đỉnh
thì có n−k đỉnh không thuộc T(k), do đó ta phải chọn chiều dài nhỏ nhất của
nhiều nhất là k(n−k) cạnh. Do k(n−k) < (n−1)
2
, nên độ phức tạp của bước chọn
e
k+1
là O(n
2
). Vì phải chọn n−1 cạnh, nên độ phức tạp của thuật toán Prim là
O(n
3
).
5.3. CÂY CÓ GỐC
5.3.1. Định nghĩa: Cây có hướng là đồ thị có hướng mà đồ thị vô
hướng nền của nó là một cây.
Cây có gốc là một cây có hướng, trong đó có một đỉnh đặc biệt, gọi là
gốc, từ gốc có đường đi đến mọi đỉnh khác của cây.
Ví dụ:
Trong cây có gốc thì gốc r có bậc vào bằng 0, còn tất cả các đỉnh khác
đều có bậc vào bằng 1.
r
a
b
c
e
g
d
i
h
l
m
j
f
k
n
o
p
q
Cây Nguyễn Thế Vinh- ĐHKH
113
Một cây có gốc thường được vẽ với gốc r ở trên cùng và cây phát triển
từ trên xuống, gốc r gọi là đỉnh mức 0. Các đỉnh kề với r được xếp ở phía dưới
và gọi là đỉnh mức 1. Đỉnh ngay dưới đỉnh mức 1 là đỉnh mức 2,
Tổng quát, trong một cây có gốc thì v là đỉnh mức k khi và chỉ khi
đường đi từ r đến v có độ dài bằng k.
Mức lớn nhất của một đỉnh bất kỳ trong cây gọi là chiều cao của cây.
Cây có gốc ở hình trên thường được vẽ như trong hình dưới đây để làm
rõ mức của các đỉnh.
Trong cây có gốc, mọi cung đều có hướng từ trên xuống, vì vậy vẽ mũi
tên để chỉ hướng đi là không cần thiết; do đó, người ta thường vẽ các cây có
gốc như là cây nền của nó.
5.3.2. Định nghĩa: Cho cây T có gốc r=v
0
. Giả sử v
0
, v
1
, , v
n-1
, v
n
là
một đường đi trong T. Ta gọi:
− v
i+1
là con của v
i
và v
i
là cha của v
i+1
.
− v
0
, v
1
, , v
n-1
là các tổ tiên của v
n
và v
n
là dòng dõi của v
0
, v
1
, , v
n-1
.
− Đỉnh treo v
n
là đỉnh không có con; đỉnh treo cũng gọi là lá hay đỉnh
ngoài; một đỉnh không phải lá là một đỉnh trong.
5.3.3. Định nghĩa: Một cây có gốc T được gọi là cây m-phân nếu mỗi
đỉnh của T có nhiều nhất là m con. Với m=2, ta có một cây nhị phân.
Trong một cây nhị phân, mỗi con được chỉ rõ là con bên trái hay con
bên phải; con bên trái của cha.
r
a
b
c
d
e
g
f
h
i
j
k
l
m
n
p
o
q
Cây Nguyễn Thế Vinh- ĐHKH
114
Cây có gốc T được gọi là một cây m-phân đầy đủ nếu mỗi đỉnh trong
của T đều có m con.
5.3.4. Định lí 1
Một cây m-phân đầy đủ có i đỉnh trong sẽ có tất cả n= m.i+1 đỉnh và có
(m−1)i+1 lá.
Chứng minh:
Mọi đỉnh trong của cây m-phân đầy đủ đều có bậc ra là m, còn lá có
bậc ra là 0, vậy số cung của cây này là mi và do đó số đỉnh của cây là m.i+1.
Gọi l là số lá thì ta có l+i=m.i+1, nên l=(m−1)i+1.
5.3.5. Định lí 2
1) Một cây m-phân có chiều cao h thì có nhiều nhất là m
h
lá.
2) Một cây m-phân có l lá thì có chiều cao h ≥ log
m
l.
Chứng minh:
1) Mệnh đề được chứng minh bằng quy nạp theo h. Mệnh đề hiển
nhiên đúng khi h=1. Giả sử mọi cây có chiều cao k ≤ h−1 đều có nhiều nhất
m
k-1
lá (với h≥2). Xét cây T có chiều cao h. Bỏ gốc khỏi cây ta được một rừng
gồm không quá m cây con, mỗi cây con này có chiều cao ≤ h−1. Do giả thiết
quy nạp, mỗi cây con này có nhiều nhất là m
h-1
lá. Do lá của những cây con
này cũng là lá của T, nên T có nhiều nhất là m.m
h-1
=m
h
lá.
2) l ≤ m
h
⇔ h ≥ log
m
l.
Cây m- phân có gốc và độ cao h được gọi là cân đối nếu tất cả các lá
đều ở mức h hoặc (h-1)
5.4. DUYỆT CÂY NHỊ PHÂN
5.4.1. Định nghĩa: Trong nhiều trường hợp, ta cần phải “điểm danh”
hay “thăm” một cách có hệ thống mọi đỉnh của một cây nhị phân, mỗi đỉnh
chỉ một lần. Ta gọi đó là việc duyệt cây nhị phân hay đọc cây nhị phân.
Có nhiều thuật toán duyệt cây nhị phân, các thuật toán đó khác nhau
chủ yếu ở thứ tự thăm các đỉnh.
Cây nhị phân T có gốc r được ký hiệu là T(r). Giả sử r có con bên trái là
u, con bên phải là v. Cây có gốc u và các đỉnh khác là mọi dòng dõi của u
Cây Nguyễn Thế Vinh- ĐHKH
115
trong T gọi là cây con bên trái của T, ký hiệu T(u). Tương tự, ta có cây con
bên phải T(v) của T. Một cây T(r) có thể không có cây con bên trái hay bên
phải.
Sau đây là ba trong các thuật toán duyệt cây nhị phân T(r). Các thuật
toán đều được trình bày đệ quy. Chú ý rằng khi cây T(x) chỉ là môt đỉnh x thì
“duyệt T(x)” có nghĩa là “thăm đỉnh x”.
Ví dụ:
5.4.2. Các thuật toán duyệt cây nhị phân
1) Thuật toán tiền thứ tự: (preorder)
1. Thăm gốc r.
2. Duyệt cây con bên trái của T(r) theo tiền thứ tự.
3. Duyệt cây con bên phải của T(r) theo tiền thứ tự.
Duyệt cây nhị phân T(a) trong hình trên theo tiền thứ tự:
Kết quả duyệt cây T(a) theo tiền thứ tự là:
a, b, d, g, l, h, e, i, m, n, c, f, j, o, p, k, q, s.
2) Thuật toán trung thứ tự: (inorder)
1. Duyệt cây con bên trái của T(r) theo trung thứ tự.
2. Thăm gốc r.
3. Duyệt cây con bên phải của T(r) theo trung thứ tự.
Duyệt cây nhị phân T(a) trong hình trên theo trung thứ tự:
Kết quả duyệt cây T(a) theo trung thứ tự là:
g, l, d, h, b, m, i, n, e, a, c, o, j, p, f, q, k, s.
a
b
c
d
e
f
g
h
i
j
k
q
s
l
m
n
o
p
Cây Nguyễn Thế Vinh- ĐHKH
116
3) Thuật toán hậu thứ tự: (postorder)
1. Duyệt cây con bên trái của T(r) theo hậu thứ tự.
2. Duyệt cây con bên phải của T(r) theo hậu thứ tự.
3. Thăm gốc r.
Duyệt cây nhị phân T(a) trong hình trên theo hậu thứ tự:
Kết quả duyệt cây T(a) theo trung thứ tự là:
l, g, h, d, m, n, i, e, b, o, p, j, q, s, k, f, c, a.
5.4.3. Ký pháp Ba Lan
Xét biểu thức đại số sau đây:
(a+b)*(c−d/2) (1)
Ta vẽ một cây nhị phân như hình dưới đây, trong đó mỗi đỉnh trong
mang dấu của một phép tính trong (1), gốc của cây mang phép tính sau cùng
trong (1), ở đây là dấu nhân ký hiệu là *, mỗi lá mang một số hoặc một chữ
đại diện cho số.
Duyệt cây nhị phân trong hình trên theo trung thứ tự là:
a + b * c −
−−
− d / 2 (2)
và đây là biểu thức (1) đã bỏ đi các dấu ngoặc.
Đối với cây trong hình thứ nhất, nếu duyệt theo tiền thứ tự, ta có
* + a b − c / d 2 (3)
và nếu duyệt theo hậu thứ tự, ta có:
a b + c d 2 / − * (4)
+
−
a
b
c
/
2
d
*
Cây Nguyễn Thế Vinh- ĐHKH
117
Vì vậy, nếu ta viết các biểu thức trong đại số, trong lôgic bằng cách
duyệt cây tương ứng theo tiền thứ tự hoặc hậu thứ tự thì ta không cần dùng
các dấu ngoặc mà không sợ hiểu nhầm.
Người ta gọi cách viết biểu thức theo tiền thứ tự (tiền tố) là ký pháp Ba
Lan, còn cách viết theo hậu thứ tự (hậu tố) là ký pháp Ba Lan đảo, để ghi nhớ
đóng góp của nhà toán học và lôgic học Ba Lan Lukasiewicz (1878-1956)
trong vấn đề này.
Việc chuyển một biểu thức viết theo ký pháp quen thuộc (có dấu ngoặc)
sang dạng ký pháp Ba Lan hay ký pháp Ba Lan đảo hoặc ngược lại, có thể
thực hiện bằng cách vẽ cây nhị phân tương ứng sau đó áp dụng thuật toán
duyệt cây theo thứ tự trước; thứ tự sau như đã làm đối với biểu thức (1).
Như vậy việc tính giá trị của một biểu thức trong tin học thực hiện hai
thao tác cơ bản
(1) Chuyển đổi biểu thức dạng trung tố sang hậu tố
(2) Tính giá trị biểu thức hậu tố
Trong tài liệu này không đề cập tới hai thuật toán trên bạn đọc có thể
tìm hiểu qua các ứng dụng của STACK
5.4.4. Phép quay trái và phải một cây nhị phân
Giả sử cho một cây nhị phân T. Với mỗi một nút u của cây T ta gọi
u.left và u.right tương ứng là con trái và con phải của u. Khi đó phép quay trái
và quay phải gọi chung là phép quay, được minh họa bởi hình dưới đây.
Cây gốc A quay phải thành cây gốc B và ngược lại cây gốc B quay trái
thành cây gốc A.
A
B
C
D
E
B
D
A
E
C
Không có nhận xét nào:
Đăng nhận xét