Bài giảng Toán tổ hợp - Chương 5: Cây - Nguyễn Anh Thi

CÂY 
Chương 5 
2 
 Định nghĩa và tính chất 
 Cây khung ngắn nhất 
 Cây có gốc 
 Phép duyệt cây 
Nội dung 
3 
Định nghĩa. Cây (tree) là đồ thị vô hướng, liên thông 
va ̀ không có chu trình 
A 
C 
B 
D 
E F 
G1 
A 
C 
B 
D 
E F 
G2 
1. Định nghĩa và tính chất 
G1 là cây, G2 không phải cây 
4 
Cây 
5 
Định nghĩa. Rừng (forest) là đồ thị vô hướng không 
có chu trình 
Nhận xét. Rừng là đồ thị mà mỗi thành phần liên thông 
của nó là một cây. 
A 
D 
B 
E 
G I 
H 
J 
L 
K F C 
Rừng 
6 
Rừng 
7 
Định lý: Cho đồ thị vô hướng T có n đỉnh. Khi đó các 
phát biểu sau là tương đương: 
1) T là 1 cây 
2) T không chứa chu trình và có n-1 cạnh 
3) T liên thông và có n-1 cạnh 
4) T liên thông và mỗi cạnh của nó đều là cầu 
5) Giữa hai đỉnh bất kỳ của T có đúng một đường 
đi nối chúng với nhau 
6) T không chứa chu trình nhưng khi thêm vào 
một cạnh ta thu được đúng một chu trình 
Tính chất của cây 
8 
Hệ quả. 
a) Một cây có ít nhất 2 đỉnh treo 
b) Nếu G là một rừng có n đỉnh và có p cây thì số 
cạnh của G là m=n-p 
9 
Định nghĩa: Một cây T được gọi là cây khung (hay 
cây tối đại, cây bao trùm) của đồ thị G=(V, E) nếu T là 
đồ thị con của G và chứa tất cả các đỉnh của G. 
A 
C 
B E 
D 
F 
Cây khung của đồ thị 
Ví dụ. Cho đồ thị 
Hãy tìm cây khung của G? 
10 
Nhận xét. Với 1 đồ thị cho trước, có thể có vài cây khung 
của đồ thị đó 
A 
C 
B E 
D 
F A 
C 
B E 
D 
F 
Đáp án. Một số cây khung của G 
Cây khung của đồ thị 
A 
C 
B E 
D 
F 
11 
Định lý. Mọi đồ thị liên thông đều có cây khung 
Định lý (Cayley) Số cây khung của đồ thị Kn là n
n-2 
A 
C B 
D E 
Số cây khung 44-2=16 
Ví dụ: abc, bcd, cda, dab, abf, acf, bdf, ... 
e 
a 
b 
c 
f d 
Số cây khung 55-2=125 
12 
Bài toán: Cho G là đồ thị vô hướng liên thông, hãy 
tìm 1 cây khung của đồ thị G. 
Lời giải 
• Thuật toán tìm kiếm theo chiều rộng (BFS) 
• Thuật toán tìm kiếm theo chiều sâu (DFS) 
Tìm một cây khung của đồ thị 
13 
Cho G là đồ thị liên thông với tập đỉnh {v1, v2, , vn} 
 Bước 0: thêm v1 như là gốc của cây rỗng. 
 Bước 1: thêm vào các đỉnh kề v1 và các cạnh nối v1 
với chúng. Những đỉnh này là đỉnh mức 1 trong cây. 
 Bước 2: đối với mọi đỉnh v mức 1, thêm vào các 
cạnh kề với v vào cây sao cho không tạo nên chu 
trình. Ta thu được các đỉnh mức 2. 
. 
Tiếp tục quá trình này cho tới khi tất cả các đỉnh của đồ 
thị được ghép vào cây. Cây T có được là cây khung của 
đồ thị. 
Tìm kiếm theo chiều rộng (BFS) 
14 
Ví dụ. Tìm một cây khung của đồ thị G. 
 b f 
 e 
 d 
 i 
Chọn e làm gốc 
Các đỉnh mức 1 là: b, d, f, i 
 Chọn các đỉnh kề với e. 
 a 
 b 
 g 
 f e 
 c l 
 d 
 k m 
 h 
 j i 
15 
 a 
 b 
 g 
 f e 
 c l 
 d 
 k m 
 h 
 j i 
 a 
 g 
 c 
 k h 
 j 
 b 
 f 
 e 
 d 
 i 
 g và j là con của f, 
Các đỉnh mức 2 là: a, c, h, g, j, k 
 Thêm a và c làm con của b, 
 h là con duy nhất của d, 
 k là con duy nhất của i, 
16 
 l m 
 a 
 b 
 g 
 f 
 e 
 c 
 d 
 k 
 h 
 j 
 i 
Cuối cùng thêm l và m là con của g và k tương ứng 
Các đỉnh mức 3 là: l, m 
 a 
 b 
 g 
 f e 
 c l 
 d 
 k m 
 h 
 j i 
 Ta có được cây khung cần tìm 
17 
D 
F 
H 
E 
I 
J 
G 
C 
B 
A 
K 
Ví dụ. Tìm cây khung của đồ thị bằng thuật toán BFS 
với D là đỉnh bắt đầu 
18 
Đáp án. 
19 
 Chọn một đỉnh tùy ý của đồ thị làm gốc. 
 Xây dựng đường đi từ đỉnh này bằng cách lần lượt 
ghép các cạnh sao cho mỗi cạnh mới ghép sẽ nối 
đỉnh cuối cùng trên đường đi với một đỉnh còn 
chưa thuộc đường đi. Tiếp tục ghép thêm cạnh 
vào đường đi chừng nào không thể thêm được 
nữa. 
 Nếu đường đi qua tất cả các đỉnh của đồ thị thì 
cây do đường đi này tạo nên là cây khung. 
Cho G là đồ thị liên thông với tập đỉnh {v1, v2, , vn} 
Tìm kiếm theo chiều sâu (DFS) 
20 
 Nếu chưa thì lùi lại đỉnh trước đỉnh cuối cùng của 
đường đi và xây dựng đường đi mới xuất phát từ 
đỉnh này đi qua các đỉnh còn chưa thuộc đường đi. 
 Nếu điều đó không thể làm được thì lùi thêm một 
đỉnh nữa trên đường đi, tức là lùi hai đỉnh trên 
đường đi và thử xây dựng đường đi mới. 
 a 
 b 
 g 
 f 
 e 
 c 
 d 
 k h 
 j i 
Ví dụ. Tìm một cây 
khung của đồ thị với 
f là đỉnh gốc 
21 
 a 
 b 
 g 
 f 
 e 
 c 
 d 
 k h 
 j i f 
 g 
 h 
 k 
 j 
Thêm các hậu duệ của f : g, h, k, j 
Lùi về k không thêm được cạnh nào, tiếp tục lùi về h 
22 
 a 
 b 
 g 
 f 
 e 
 c 
 d 
 k h 
 j i 
Lùi về c và thêm b làm con thứ hai của nó . 
 d 
 e 
 c 
 a b 
 Thêm i làm con thứ hai của h 
 j 
 f 
 g 
 h 
 k 
 i 
và lùi về f. 
 Lại thêm các hậu duệ của f : d, e, c, a 
Cây thu được là cây khung của đồ thị đã cho 
23 
D 
F 
H 
E 
I 
J 
G 
C 
B 
A 
K 
Ví dụ. Tìm một cây khung của đồ thị bằng thuật toán 
DFS với A là đỉnh bắt đầu 
24 
Định nghĩa. Đồ thị G = (V,E) gọi là đồ thị có trọng 
số (hay chiều dài, trọng lượng) nếu mỗi cạnh e được 
gán với một số thực w(e). Ta gọi w(e) là trọng 
lượng của e. 
 Độ dài của đường đi từ u đến v bằng tổng độ dài 
các cạnh mà đường đi qua. 
 Trọng lượng của một cây T của G bằng với tổng 
trọng lượng các cạnh trong cây 
 Cây khung ngắn nhất là cây khung có trọng 
lượng nhỏ nhất của G. 
Đồ thị có trọng số 
25 
Định nghĩa. Cho G = (V, E), V = {v1,v2,,vn} là đơn 
đồ thị có trọng số. Ma trận khoảng cách của G là 
ma trận D= (dij) xác định như sau: 
( )
0
ij i ji j
i j
khi i j
d khi v v E
khi v v E
w v v
Ma trận khoảng cách (trọng số) 
26 
C 
A B 
D 
E 
12 
7 
15 
6 
5 
5 
10 
16 0 12 7 5
12 0 15 16 6
7 15 0 10
5 16 0 5
6 10 5 0
Ma trận khoảng cách 
Ví dụ. Tìm ma trận khoảng cách của đồ thị sau 
27 
Có nhiều thuật toán xây dựng cây khung ngắn nhất: 
– Thuật toán Boruvka 
– Thuật toán Kruskal 
– Thuật toán Jarnik – Prim 
– Phương pháp Dijkstra 
– Thuật toán Cheriton – Tarjan 
– Thuật toán Chazelle 
–  
Thuật toán tìm cây khung ngắn nhất 
28 
Input: Đồ thị G=(X, E) liên thông, X gồm n đỉnh 
Output: Cây khung ngắn nhất T=(V, U) của G 
Bước 1. Sắp xếp các cạnh trong G tăng dần theo 
trọng lượng; khởi tạo T := . 
Bước 2. Lần lượt lấy từng cạnh e thuộc danh sách 
đã sắp xếp. Nếu T+{e} không chứa chu trình thì 
thêm e vào T: T := T+{e}. 
Bước 3. Nếu T đủ n-1 cạnh thì dừng; ngược lại, 
lặp bước 2. 
Thuật toán Kruskal 
29 
A B 
E 
F 
C 
D 
8 
5 
AE AC CD DE BD AF AD BC EF AB 
1 1 1 2 3 3 4 5 6 8 
1 
1 
1 
2 
3 
6 
3 
4 
Ví dụ. Tìm cây khung ngắn nhất của đồ thị sau 
Giải. Sắp xếp các cạnh 
Thuật toán Kruskal 
30 
A B 
E 
F 
C 
D 
8 
5 
AE AC CD DE BD AF AD BC EF AB 
1 1 1 2 3 3 4 5 6 8 
1 
1 
2 
3 
6 
3 
4 1 
Thuật toán Kruskal 
31 
A B 
E 
F 
C 
D 
8 
5 
AE AC CD DE BD AF AD BC EF AB 
1 1 1 2 3 3 4 5 6 8 
1 
2 
3 
6 
3 
4 1 
1 
Thuật toán Kruskal 
32 
A B 
E 
F 
C 
D 
8 
5 
AE AC CD DE BD AF AD BC EF AB 
1 1 1 2 3 3 4 5 6 8 
6 
3 
4 1 
1 
1 
2 
3 
Thuật toán Kruskal 
33 
A B 
E 
F 
C 
D 
8 
5 
AE AC CD DE BD AF AD BC EF AB 
1 1 1 2 3 3 4 5 6 8 
6 
3 
4 1 
1 
1 
2 
3 
Thuật toán Kruskal 
34 
A B 
E 
F 
C 
D 
3 
1 
1 
1 
3 
Như vậy T = { AE, CD, AC, BD, AF } là khung ngắn 
nhất với trọng lượng: 9 
Thuật toán Kruskal 
35 
C 
A B 
D 
E 
F 
10 
12 
9 
7 
15 
6 
5 
15 
10 
8 
16 
Ví dụ. Tìm cây khung ngắn nhất của đồ thị sau 
Thuật toán Kruskal 
36 
Ví dụ. Tìm cây khung ngắn nhất của đồ thị sau 
Thuật toán Kruskal 
37 
Ví dụ. Dùng thuật toán Kruskal để tìm cây khung nhỏ 
nhất của đồ thị sau: 
A 
C 
B 
E 
D F 
G 
H 
K 
I 
J 
2 
4 
6 
9 3 
6 
7 
2 6 
8 
1 
9 3 
6 
7 
4 
5 
5 
5 
6 
Thuật toán Kruskal 
38 
Input: Đồ thị liên thông G=(X, E), X gồm n đỉnh 
Output: Cây khung ngắn nhất T=(V, U) của G 
Bước 1. Chọn tùy ý v X và khởi tạo V := { v }; 
U := ; 
Bước 2. Chọn cạnh e có trọng lượng nhỏ nhất 
trong các cạnh wv mà w X\V và v V 
Bước 3. V := V  {w}; U := U  {e} 
Bước 4. Nếu U đủ n-1 cạnh thì dừng, ngược lại 
lặp từ bước 2. 
Thuật toán Prim 
39 
C 
A B 
D 
E 
F 
V = {F, C, A, D, E, B} U = {FC, CA, AD, DE, EB} 
10 
12 
9 
7 
15 
6 
5 
5 
10 
8 
16 
Trọng lượng: 32 
Thuật toán Prim 
Ví dụ. Tìm cây khung ngắn nhất của đồ thị sau 
40 
41 
Ví dụ. Tìm cây khung ngắn nhất của đồ thị sau 
42 
Ví dụ. Dùng thuật toán Prim để tìm cây khung nhỏ 
nhất của đồ thị sau: 
A 
C 
B 
E 
D F 
G 
H 
K 
I 
J 
2 
4 
6 
9 3 
6 
7 
2 6 
8 
1 
9 3 
6 
7 
4 
5 
5 
5 
6 
43 
Định nghĩa. Cho T là một cây. Chọn một đỉnh r của cây 
gọi là gốc. Vì có đường đi sơ cấp duy nhất từ gốc tới 
mỗi đỉnh của đồ thị nên ta định hướng mỗi cạnh là 
hướng từ gốc đi ra. Cây cùng với gốc sinh ra một đồ thị 
có hướng gọi là cây có gốc 
43 
3. Cây có gốc 
Cây T Cây gốc 0 Cây gốc 4 
3 
0 
1 
4 
6 
7 5 
2 
3 
0 
1 4 
6 7 
5 2 
3 
0 
1 
4 
6 7 
5 
2 
44 
Một số ví dụ về cây có gốc 
• Cấu trúc thư mục trên đĩa 
• Gia phả của một họ tộc 
• Một biểu thức số học 
(7+2/3) x (7-2) x 
+ - 
7 2 7 / 
2 3 
Ví dụ 
45 
Định nghĩa. Cho cây có gốc r. 
 Gốc r được gọi là đỉnh mức 0 (level 0). 
 Các đỉnh kề với gốc r được xếp ở phía dưới gốc 
và gọi là đỉnh mức 1 (level 1). 
 Đỉnh sau của đỉnh mức 1 (xếp phía dưới đỉnh 
mức1) gọi là đỉnh mức 2.  
 Level(v) = k đường đi từ gốc r đến v qua k 
cung. 
 Độ cao của cây là mức cao nhất của các đỉnh. 
 45 
Một số khái niệm 
46 
---------------------------------level 0 
---------------------------------------level 1 
----------------------------------------------level 2 
--------------------------------------------------level 3 
---------------------------------------------level 4 
47 
Định nghĩa. Cho cây có gốc r 
 Nếu uv là một cung của T thì u được gọi là cha 
của v, còn v gọi là con của u. 
 Đỉnh không có con gọi là lá (hay đỉnh ngoài). Đỉnh 
không phải là lá gọi là đỉnh trong. 
 Hai đỉnh có cùng cha gọi là anh em. 
 Nếu có đường đi v1v2vk thì v1, v2,.., vk-1 gọi là tổ 
tiên của vk. Còn vk gọi là hậu duệ của v1, v2,.., vk-1. 
 Cây con tại đỉnh v là cây có gốc là v và tất cả các 
đỉnh khác là hậu duệ của v trong cây T đã cho. 
47 
Một số khái niệm 
48 
Định nghĩa. Cho T là cây có gốc. 
a) T được gọi là cây k-phân nếu mỗi đỉnh của T 
có nhiều nhất là k con. 
b) Cây 2-phân được gọi là cây nhị phân. 
c) Cây k-phân đủ là cây mà mọi đỉnh trong có 
đúng k con. 
d) Cây k-phân với độ cao h được gọi là cân đối 
nếu các lá đều ở mức h hoặc h – 1. 
48 
49 
Một số khái niệm 
50 
Định nghĩa. Cho T là cây nhị phân có gốc là r. Ta có 
thể biểu diễn T như hình vẽ dưới với hai cây con tại r 
là TL và TR ,chúng lần lượt được gọi là cây con bên 
trái và cây con bên phải của T. 
r 
TL TR 
50 
51 
 Chúng ta có thê ̉ biểu diễn cây như 1 đồ thị 
• Ma trận 
• Danh sách 
Nhận xét: Vì số cạnh của cây rất thưa (n-1 cạnh) nên 
dùng ma trận để biểu diễn cây là không hiệu quả 
Biểu diễn cây 
52 
Biểu diễn cây bằng danh sách kề 
3 
0 
1 9 4 
6 8 7 5 2 
Đỉnh Đỉnh kề 
0 1 9 4 
1 3 6 
2 Ø 
3 Ø 
4 7 5 2 
5 Ø 
6 Ø 
7 Ø 
8 Ø 
9 8 
Biểu diễn cây 
53 
 Bài toán 1: Kiểm tra xem đồ thị G có phải là 1 cây 
không 
 Bài toán 2: Tìm gốc của cây 
 Bài toán 3: Tính độ cao của cây với gốc là đỉnh r 
Một số bài toán liên quan tới cây 
54 
Định nghĩa. Duyệt cây là liệt kê tất các đỉnh của 
cây theo một thứ tự nào đó thành một dãy, mỗi đỉnh 
chỉ xuất hiện một lần. 
Có 2 phép duyệt cây 
- Phép duyệt tiền thứ tự (Preorder traversal) 
- Phép duyệt hậu thứ tự (Posorder traversal). 
54 
4. Phép duyệt cây 
55 
 Đến gốc r. 
 Dùng phép duyệt tiền thứ tự để duyệt các cây con 
T1 rồi cây con T2  từ trái sang phải. 
Phép duyệt tiền thứ tự 
Ví dụ. Duyệt cây sau 
14 
84 43 
13 16 33 97 
64 99 72 53 
35 
56 
 Push the root onto the stack. 
 While the stack is not empty 
• pop the stack and visit it 
• push its two children 
14 
84 43 
13 16 33 97 
64 99 72 53 
35 
Do đó các đỉnh lần lượt được duyệt là: 
 14, 84, 35, 13, 53, 16, 99, 72, 43, 33, 64, 97 
57 
 Dùng phép duyệt hậu thứ tự để lần lượt duyệt cây 
con T1, T2,. từ trái sang phải. 
 Đến gốc r. 
Phép duyệt hậu thứ tự 
Ví dụ. Duyệt cây sau 
14 
84 43 
13 16 33 97 
64 99 72 53 
35 
58 
 Push the root onto the stack. 
 While the stack is not empty 
• pop the stack and visit it 
• push its two children 
14 
84 43 
13 16 33 97 
64 99 72 53 
35 
Do đó các đỉnh lần lượt được duyệt là: 
 35, 53, 13, 16, 99, 72, 43, 33, 64, 97 
59 
 Duyệt cây con bên trái TL theo trung thứ tự. 
 Đến gốc r. 
 Duyệt cây con bên phải theo trung thứ tự. 
59 
Đối với cây nhị phân, ta có thêm phép duyệt trung thứ 
tự cho cây nhị phân (Inorder traversal) 
Ví dụ. Duyệt cây sau 14 
84 43 
13 16 33 97 
64 99 72 53 
Duyệt cây nhị phân 
60 
 Push the root onto the stack. 
 While the stack is not empty 
• pop the stack and visit it 
• push its two children 
14 
84 43 
13 16 33 97 
64 99 72 53 
Do đó các đỉnh lần lượt được duyệt là: 
 53, 13, 84, 99, 16, 72, 14, 33, 64, 43, 97 
61 
8 5 
 + 
Gốc 
Cây nhị phân biểu thức 
Xét cây như sau 
Khi đó, theo phép duyệt 
- Tiền thứ tự: + 8 5 
- Hậu thứ tự: 8 5 + 
- Trung thứ tự: 8 + 5 
62 
Định nghĩa. Cây nhị phân của biểu thức là cây nhị 
phân mà 
 - Mỗi biến số được biểu diễn bởi một lá. 
 - Mỗi đỉnh trong biểu diễn một phép toán với các 
thành tố là cây con tại đỉnh ấy. 
Cây con bên trái và bên phải của một đỉnh trong biểu 
diễn cho biểu thức con, giá trị của chúng là thành tố 
mà ta áp dụng cho phép toán tại gốc của cây con. 
Cây nhị phân biểu thức 
63 
* 
 + 
4 
3 
2 
Kết quả? 
( 4 + 2 ) * 3 = 18 
Tính giá trị của biểu thức được biểu diễn bằng đồ thị sau 
64 
Định nghĩa. Ta gọi kết quả có được khi duyệt cây nhị 
phân của biểu thức theo phép duyệt 
- Trung thứ tự là trung tố 
- Tiền thứ tự là tiền tố và được gọi là ký pháp Ba 
Lan 
- Hậu thứ tự là hậu tố và được gọi là ký pháp Ba 
Lan ngược 
65 
* 
 + 
4 
3 
2 
Khi đó 
 Trung tố: 4 + 2 * 3 
 Tiền tố: * + 4 2 3 Ký pháp Ba lan 
 Hậu tố: 4 2 + 3 * Ký pháp Ba lan ngược 
66 
+ 
- / 
* 
^ 
9 3 
2 3 5 2 
Ví dụ. Cho cây nhị 
phân T của biểu 
thức 
Hãy tìm tiền tố, trung tố, hậu tố của G? 
67 
Nhận xét. Để tính biểu thức khi có ký pháp Ba Lan ta 
tính từ phải sang trái: Bắt đầu từ bên phải, khi gặp 
một phép toán thì phép toán này được thực hiện cho 
2 thành tố ngay bên phải nó, kết quả này là thành tố 
cho phép toán tiếp theo. 
Ví dụ. Tính giá trị của ký pháp Ba Lan sau: 
a) − ∗ 2 / 8 4 3 
b) ^ − ∗ 3 3 ∗ 4 2 5 
c) + − ^ 3 2 ^ 2 3 / 6 − 4 2 
d) ∗ + 3 + 3 ^ 3 + 3 3 3 
68 
Giải. a) − ∗ 2 / 8 4 3 
  − ∗ 2 2 3 
  − 4 3 
  1 
b) ^ − ∗ 3 3 ∗ 4 2 5 
  ^ − ∗ 3 3 8 5 
  ^ − 9 8 5 
  ^ 1 5 
  1 
c) + − ^ 3 2 ^ 2 3 / 6 − 4 2 ? 
d) ∗ + 3 + 3 ^ 3 + 3 3 3 ? 
69 
Nhận xét. Để tính biểu thức khi có ký pháp Ba Lan 
ngược, ta tính từ bên trái, khi gặp một phép toán thì 
phép toán này được thực hiện cho 2 thành tố ngay 
bên trái nó, kết quả này là thành tố cho phép toán 
tiếp theo. 
Ví dụ. Tính giá trị của ký pháp Ba Lan ngược sau: 
a) 5 2 1−−3 1 4 ++ ∗ 
b) 9 3 / 5 + 7 2 − ∗ 
c) 3 2 ∗ 2 ^ 5 3 − 8 4 / ∗ −