Bài giảng Lý thuyết đồ thị - Bài 4: Cây (Tree)

Bài 4 
Cây (Tree) 
Các khái niệm cơ bản về Cây 
Định nghĩa: Cây là một đơn đồ thị vô hướng , liên thông và không chứa chu trình . 
Ví dụ: Trong các đồ thị sau, đồ thị nào là cây? 
Cả 3 đồ thị trên đều là cây. 
2 
Cây (tt) 
VD: Trong các đồ thị sau, đồ thị nào là cây? 
G1, G2 là cây. G3 không là cây do có chứa chu trình, G4 không liên thông 
3 
Cây (tt) 
Định nghĩa: Nếu G là một đồ thị vô hướng và không chứa chu trình thì G được gọi là một rừng . Khi đó mỗi thành phần liên thông của G sẽ là một cây. 
VD: 
Đồ thị trên là rừng có 3 cây 
4 
Tính chất của cây 
Định lý: Cho T là một đồ thị vô hướng. Khi đó, các điều sau đây là tương đương: 
T là cây. 
T không chứa chu trình và có n – 1 cạnh. 
T liên thông và có n – 1 cạnh. 
T liên thông và mỗi cạnh của T đều là cạnh cắt (cầu). 
Hai đỉnh bất kỳ của T được nối với nhau bằng đúng 1 đường đi đơn. 
T không chứa chu trình nhưng nếu thêm 1 cạnh bất kỳ vào T thì ta sẽ được thêm đúng 1 chu trình. 
5 
Tính chất của cây (tt) 
Chứng minh định lý: 
(1)  (2): T là cây  T không chứa chu trình và có n-1 cạnh 
Hiển nhiên T không chứa chu trình (do T là cây) 
Ta chỉ cần chứng minh T có n-1 cạnh. 
Xét T n là cây có n đỉnh. Ta sẽ chứng minh quy nạp theo n 
n = 2, Cây có 2 đỉnh thì có 1 cạnh. Đúng. 
Giả sử mọi cây có k đỉnh thì sẽ có k-1 cạnh 
Xét T k+1 là cây có k + 1 đỉnh. Dễ thấy rằng trong cây T k+1 luôn tồn tại ít nhất 1 đỉnh treo. 
Loại đỉnh treo này (cùng với cạnh nối) ra khỏi T k+1 ta được đồ thị T’ có k đỉnh. Dễ thấy T’ vẫn liên thông và không có chu trình (do T k+1 không có chu trình) 
Suy ra T’ là cây. Theo giả thiết quy nạp, T’ có k đỉnh thì sẽ có k-1 cạnh. Vậy cây T k+1 có k cạnh. (đpcm) 
6 
Tính chất của cây (tt) 
Chứng minh định lý (tt): 
(2)  (3): T không chứa chu trình và có n-1 cạnh  T liên thông và có n-1 cạnh 
Hiển nhiên T có n-1 cạnh (theo giả thiết) 
Ta chỉ cần chứng minh T liên thông. 
Giả sử T có k thành phần liên thông với số đỉnh lần lượt là n 1 ,, n k . 
Khi đó mỗi thành phần liên thông của T sẽ là một cây và sẽ có số cạnh lần lượt là n 1 -1, n 2 -1,, n k -1. 
Suy ra, số cạnh của T sẽ là n 1 -1 + n 2 -1 ++ n k -1 = n – k. 
Theo giả thiết, số cạnh của cây là n-1. Từ đó suy ra k = 1 hay T chỉ có 1 thành phần liên thông. Suy ra T liên thông (đpcm). 
7 
Tính chất của cây (tt) 
Chứng minh định lý (tt): 
(3)  (4): T liên thông và có n-1 cạnh  T liên thông và mỗi cạnh của T đều là cạnh cắt (cầu) 
Hiển nhiên T liên thông (theo giả thiết) 
Ta chỉ cần chứng minh mỗi cạnh của T đều là cạnh cắt (cầu). 
Xét (u,v) là cạnh bất kỳ của T. Nếu bỏ (u,v) ra khỏi T, ta sẽ được đồ thị T’ có n đỉnh và n-2 cạnh. 
Đồ thị có n đỉnh và n-2 cạnh thì không thể liên thông. 
Vậy nếu bỏ cạnh (u,v) ra thì sẽ làm mất tính liên thông của đồ thị. Suy ra (u,v) là cạnh cắt (cầu). (đpcm). 
8 
Tính chất của cây (tt) 
Chứng minh định lý (tt): 
(4)  (5): T liên thông và mỗi cạnh của T đều là cạnh cắt (cầu)  Giữa hai đỉnh bất kỳ của T luôn tồn tại đúng 1 đường đi đơn 
Xét u, v là hai đỉnh bất kỳ trong T. 
Do T liên thông nên luôn tồn tại đường đi giữa u và v. Ta sẽ chứng minh đường đi này là duy nhất. 
Giả sử có hai đường đi đơn khác nhau giữa u và v. Khi đó hai đường đi này sẽ tạo thành một chu trình. 
Suy ra, các cạnh trên chu trình này sẽ không thể là cạnh cắt được (???) – Mâu thuẫn. 
Vậy giữa u và v chỉ có thể tồn tại đúng 1 đường đi đơn. (đpcm) 
9 
Tính chất của cây (tt) 
Chứng minh định lý (tt): 
(5)  (6): Giữa hai đỉnh bất kỳ của T luôn tồn tại đúng 1 đường đi đơn  T không chứa chu trình, nhưng nếu thêm vào 1 cạnh bất kỳ thì sẽ phát sinh đúng 1 chu trình 
T không thể có chu trình, vì nếu có chu trình thì giữa hai đỉnh trên chu trình này sẽ có 2 đường đi đơn khác nhau – mâu thuẫn với GT. 
Giả sử ta thêm vào T cạnh (u,v) bất kỳ (trước đó không có cạnh này trong T). 
Khi đó cạnh này sẽ tạo với đường đi duy nhất giữa u và v trong T tạo thành 1 chu trình duy nhất. (Vì nếu tạo thành 2 chu trình thì chứng tỏ trước đó có 2 đường đi khác nhau giữa u và v – mâu thuẫn với giả thiết) 
10 
Tính chất của cây (tt) 
Chứng minh định lý (tt): 
(6)  (1): T không chứa chu trình, nhưng nếu thêm vào 1 cạnh bất kỳ thì sẽ phát sinh đúng 1 chu trình  T là cây 
Hiển nhiên T không chứa chu trình (theo giả thiết). 
Giả sử T không liên thông. Khi đó T sẽ có nhiều hơn 1 thành phần liên thông 
Suy ra, nếu thêm vào một cạnh bất kỳ giữa hai đỉnh thuộc 2 thành phần liên thông khác nhau sẽ không tạo thêm chu trình nào – mâu thuẫn với giả thiết. 
Vậy, T phải liên thông. Suy ra T là cây. (đpcm) 
11 
Cây có gốc 
Trong một số cây, một đỉnh đặc biệt được chọn làm gốc 
Đường đi từ gốc đến các đỉnh được định hướng từ gốc đến đỉnh đó 
Suy ra một cây cùng với gốc sẽ sinh ra đồ thị có hướng, được gọi là cây có gốc. 
Trong cây có gốc: 
Mỗi đỉnh chỉ có một cha duy nhất – là đỉnh mà trực tiếp đi đến nó trên đường đi từ gốc 
Mỗi đỉnh có thể không có, có 1 hoặc nhiều đỉnh con 
Các đỉnh có con được gọi là đỉnh trong, các đỉnh không có con được gọi là đỉnh ngoài (nút lá) 
12 
Cây có gốc (tt) 
VD: 
13 
Chọn đỉnh a làm gốc 
Chọn đỉnh c làm gốc 
Cây có gốc (tt) 
VD: 
Đỉnh a là đỉnh gốc 
Các đỉnh con của đỉnh a: b, c và d. 
Đỉnh cha của đỉnh f: đỉnh b (duy nhất) 
Các đỉnh trong: a, b, và c. 
Các đỉnh ngoài (lá): f, g, e và d. 
14 
Cây có gốc (tt) 
Định nghĩa: 
Cây có gốc được gọi là cây m-phân nếu tất cả các đỉnh trong của nó đều có không quá m đỉnh con. 
Cây được gọi là m-phân đầy đủ nếu tất cả các đỉnh trong của nó đều có đúng m đỉnh con 
Với m = 2, ta có cây nhị phân. 
Định nghĩa: Cây có gốc được sắp (hay có thứ tự) là cây có gốc trong đó các con của mỗi đỉnh luôn được sắp theo thứ tự nào đó (thường là lớn dần từ trái sang phải) 
15 
Các mô hình dạng cây 
Các Hydrocarbon no: 
16 
Hai đồng phân của Butane 
Các mô hình dạng cây (tt) 
Biểu diễn các tổ chức: 
17 
Các mô hình dạng cây (tt) 
Hệ thống các tập tin, thư mục: 
18 
Các ứng dụng của cây 
Cây nhị phân tìm kiếm (đã học trong môn CTDL) 
Cây quyết định. 
Là cây có gốc 
Mỗi đỉnh ứng với một quyết định 
Mỗi cây con tại đỉnh này sẽ ứng với các kết quả có thể của quyết định đó 
Mã tiền tố Huffman. (đề tài nghiên cứu) 
19 
Cây nhị phân 
Định nghĩa: Cây nhị phân là cây mà mỗi nút có tối đa 2 cây con 
Trong thực tế thường gặp các cấu trúc có dạng cây nhị phân. Một cây tổng quát có thể biểu diễn thông qua cây nhị phân. 
20 
Cây con trái 
Cây con phải 
Cây nhị phân (tt) 
Cây nhị phân dùng để biểu diễn một biểu thức toán học: 
21 
Một số tính chất của cây nhị phân 
Số nút nằm ở mức i  2 i 
Chiều cao cây h là mức cao nhất + 1. 
Số nút lá  2 h-1 , với h là chiều cao của cây. 
Chiều cao của cây h  log 2 (số nút trong cây). 
Số nút trong cây  2 h -1. 
Đường đi (path) 
Tên các node của quá trình đi từ node gốc theo các cây con đến một node nào đó. 
22 
Mức 
Biểu diễn cây nhị phân T 
Cây nhị phân là một cấu trúc bao gồm các phần tử (nút) được kết nối với nhau theo quan hệ “cha-con” với mỗi cha có tối đa 2 con. Để biểu diễn cây nhị phân ta chọn phương pháp cấp phát liên kết. Ứng với một nút, ta sử dụng một biến động lưu trữ các thông tin sau: 
Thông tin lưu trữ tại nút. 
Địa chỉ nút gốc của cây con trái trong bộ nhớ. 
Địa chỉ nút gốc của cây con phải trong bộ nhớ. 
23 
Biểu diễn cây nhị phân T (tt) 
Để đơn giản, có thể khai báo cấu trúc dữ liệu như sau : 
	typedef struct NODE 
	{ 
	 int data; 
	 NODE* left; 
	 NODE* right; 
	}; 
	typedef struct NODE* TREE ; 
	 TREE root; 
24 
Tạo cây nhị phân 
void CreateTree( &root) 
{ 
	 int x; 
	 printf (“\nGia tri node :”); 
	x = toupper (getch()); 
	 if ( isspace (x)==0) 
	{ 
	 root=(node*)malloc(sizeof(node)); 
	root ->data=x; 
	 printf (“\nCon trai cua %c (ENTER NULL )”,x); 
	 CreateTree (root ->left); 
	 printf (“\nCon phai cua %c (ENTER NULL )”,x); 
	 CreateTree (root ->right); 
	} 
	 else root=NULL; 
} 
25 
Duyệt cây nhị phân 
Có 3 kiểu duyệt chính có thể áp dụng trên cây nhị phân: 
Duyệt theo thứ tự trước ( NLR ) 
Duyệt theo thứ tự giữa ( LNR ) 
Duyệt theo thứ tựï sau ( LRN ). 
Tên của 3 kiểu duyệt này được đặt dựa trên trình tự của việc thăm nút gốc so với việc thăm 2 cây con. 
26 
Duyệt theo thứ tự trước (Node-Left-Right) 
Ví dụ: đọc một quyển sách hay bài báo từ đầu đến cuối như minh họa trong hình bên dưới: 
27 
Duyệt theo thứ tự trước (Node-Left-Right 
28 
A 
B 
D 
H 
I 
N 
E 
J 
K 
O 
C 
F 
L 
P 
G 
M 
A 
Kết quả: 
B 
D 
H 
I 
N 
E 
J 
O 
K 
C 
F 
L 
P 
G 
M 
Duyệt theo thứ tự giữa (Left- Node-Right) 
Kiểu duyệt này trước tiên thăm các nút của cây con trái sau đó thăm nút gốc rồi đến cây con phải. 
Thủ tục duyệt có thể trình bày đơn giản như sau: 
void	LNR(TREE root) 
{ 
	if (root != NULL) 
	{ 
	LNR(root->left); 
	; 	 //Xử lý tương ứng theo nhu cầu 
	LNR(root->right); 
	} 
} 
29 
Duyệt theo thứ tự giữa (Left- Node-Right) 
30 
A 
B 
D 
H 
I 
N 
E 
J 
K 
O 
C 
F 
L 
P 
G 
M 
H 
Kết quả: 
D 
N 
I 
B 
J 
O 
E 
K 
A 
F 
P 
L 
C 
M 
G 
Duyệt theo thứ tự sau (Left-Right-Node) 
Kiểu duyệt này trước tiên thăm các nút của cây con trái sau đó thăm đến cây con phải rồi cuối cùng mới thăm nút gốc. 
Thủ tục duyệt có thể trình bày đơn giản như sau: 
void	LRN(TREE root) 
{ 
	if (root != NULL) 
	{ 
	LRN(root->left); 
	LRN(root->right); 
	 ;	//Xử lý tương ứng theo nhu cầu 
	} 
} 
31 
Duyệt theo thứ tự sau (Left-Right-Node) 
32 
A 
B 
D 
H 
I 
N 
E 
J 
K 
O 
C 
F 
L 
P 
G 
M 
H 
Kết quả: 
N 
I 
D 
O 
J 
K 
E 
B 
P 
L 
F 
M 
G 
C 
A