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

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. Đ