CÂY VÀ MỘT SỐ ỨNG DỤNG

CHƯƠNG 11

CÂY VÀ MỘT SỐ ỨNG DỤNG
NỘI DUNG
Khái niệm cây
Cây bao trùm
Cây bao trùm nhỏ nhất
Cây bao trùm lớn nhất
Cây phân cấp
Cây nhị phân
Cây biểu thức
Cây mã tối ưu

11.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: Giả sử T = (V, E) là một đồ thị vô hướng.
T là một cây nếu nó thỏa mãn hai tính chất sau:
- liên thông,
- không có chu trình.
VÍ DỤ 11.1
Đồ thị dưới đây là một cây.
Hình 11.1. Cây 7 đỉnh
11.1. KHÁI NIỆM CÂY (tiếp)
Định lý 11.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:
T là một cây.
T không có chu trình và có n - 1 cạnh.
T liên thông và có n - 1 cạnh.
T không có chu trình nhưng nếu thêm một cạnh bất kỳ nối hai đỉnh không kề nhau thì có chu trình.
T liên thông nhưng nếu bớt đi một cạnh bất kỳ thì sẽ mất tính liên thông.
Chỉ có duy nhất một đường đi nối hai đỉnh bất kỳ.
11.1. KHÁI NIỆM CÂY (tiếp)
Chứng minh: Chú ý rằng đồ thị T không có chu trình
khi và chỉ khi chu số của nó bằng 0, nghĩa là: m = n - p.
1)  2) : Vì p = 1 và m = n - p suy ra: m = n - 1.
2)  3) : m = n - p, m = n - 1 cho nên p = 1.
3)  4) : p = 1, m = n - 1 suy ra: m = n - p. Vậy thì
c(T) = 0, đồ thị T không có chu trình. Thêm một cạnh
vào thì m tăng thêm 1 còn n, p không đổi. Khi đó chu
số c(T) = m - n + p = 1. Đồ thị có một chu trình.
11.1. KHÁI NIỆM CÂY (tiếp)
Chứng minh:
4)  5) : c(T) = 0 nên m = n - p.
Phản chứng: đồ thị T không liên thông, có ít nhất hai đỉnh a, b không liên thông. Thêm cạnh (a, b) vào đồ thị vẫn không có chu trình. Mâu thuẫn với điều 4).
Vậy đồ thị phải liên thông, nghiã là p = 1. Suy ra: m = n - 1. Khi bớt đi một cạnh bất kỳ, đồ thị vẫn không có chu trình. Do đó m - 1 = n - p`. Suy ra p` = 2 và đồ thị mất tính liên thông.
11.1. KHÁI NIỆM CÂY (tiếp)
Chứng minh:
5)  6) : Đồ thị T liên thông nên có đường đi đơn nối
mỗi cặp đỉnh. Giả sử cặp đỉnh a, b được nối bằng hai
đường đi đơn khác nhau.
Khi đó có cạnh e thuộc đường đi này nhưng không
thuộc đường đi kia. Ta bỏ cạnh e này đi, đồ thị vẫn liên
thông. Trái với điều 5).
11.1. KHÁI NIỆM CÂY (tiếp)
Chứng minh:
6)  1) : Suy ra đồ thị T liên thông.
Phản chứng: T có chu trình. Vậy thì giữa hai đỉnh của
chu trình có thể nối bằng hai đường đơn khác nhau.
Mâu thuẫn với điều 6). 
11.2. CÂY BAO TRÙM
Định nghĩa 11.2
Giả sử G là một đồ thị vô hướng.
Cây T được gọi là cây bao trùm của đồ thị G nếu T là một đồ thị riêng của G.

VÍ DỤ 11.2
Đồ thị G:



Một số cây bao trùm của G:
Hình 11.2. Đồ thị có cây bao trùm
Hình 11.3. Hai cây bao trùm của đồ thị G
11.2. CÂY BAO TRÙM (tiếp)
Định lý 11.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ọn a là một đỉnh bất kỳ trong đồ thị G.
Ký hiệu: d(x) là khoảng cách giữa a và đỉnh x.
Xây dựng các tập đỉnh:
D0 = {a}, Di = { x  d(x) = i } với i  1.

11.2. CÂY BAO TRÙM (tiếp)
Hình 11.4. Cách xây dựng cây bao trùm
11.2. CÂY BAO TRÙM (tiếp)
Chú ý: Mỗi đỉnh x thuộc Di (i  1) đều có đỉnh y thuộ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 a với x thì < a, ... , y > là đường đi ngắn nhất nối a với y và y  Di-1.

11.2. CÂY BAO TRÙM (tiếp)
Chứng minh: Lập tập cạnh T như sau:
Với mỗi đỉnh x của đồ thị G, x  Di với i  1, ta lấy
cạnh nào đó nối x vớ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ới n
đỉ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 3) 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. 
11.2. CÂY BAO TRÙM (tiếp)
Định lý 11.3 (Borchardt): Số cây bao trùm của một đồ
thị vô hướng đầy đủ n đỉnh là nn – 2.

Một số thuật toán tìm cây bao trùm:
- Thuật toán sử dụng phương pháp duyệt theo chiều sâu.
- Thuật toán sử dụng phương pháp duyệt theo chiều rộng.
11.3. THUẬT TOÁN TÌM CÂY BAO TRÙM
Thuật toán 11.1 (Tìm cây bao trùm bằng phương pháp duyệt theo chiều sâu)
Dữ liệu: Biểu diễn mảng DK các danh sách kề của đồ thị vô hướng G.
Kết quả: Cây bao trùm (V, T) của đồ thị G.
11.3. THUẬT TOÁN TÌM CÂY BAO TRÙM (tiếp)
Thuật toán

1 procedure CBT_S (v) ;
2 begin
3 Duyet [v] := true ;
4 for u  DK[v] do
5 if ! Duyet [u] then
6 begin T := T  {(v, u)} ; CBT_S (u) end
7 end ;
11.3. THUẬT TOÁN TÌM CÂY BAO TRÙM (tiếp)

8 BEGIN { Chương trình chính }
9 for u  V do Duyet [u] := false ;
10 T :=  ;
CBT_S (z) ; { z là đỉnh tuỳ ý của đồ thị,
sẽ trở thành gốc của cây }
12 END.
11.3. THUẬT TOÁN TÌM CÂY BAO TRÙM (tiếp)
Tính đúng đắn của thuật toán: :
Khi ta thêm cạnh (v, u) vào tập cạnh T thì trong đồ thị
(V, T) đã có đường đi từ z tới v. Vậy thuật toán xây dựng lên đồ thị liên thông.
2. Mỗi cạnh mới (v, u) được thêm vào tập T có đỉnh v đã
được duyệt và đỉnh u đang duyệt. Vậy đồ thị đang được xây dựng không có chu trình.
Theo tính chất của phép duyệt theo chiều sâu, thủ tục CBT_S thăm tất cả các đỉnh của đồ thị liên thông G.
11.3. THUẬT TOÁN TÌM CÂY BAO TRÙM (tiếp)

Do vậy, đồ thị do thuật toán xây dựng là một cây bao trùm của đồ thị đã cho.

Độ phức tạp của thật toán là: O(n+m).

VÍ DỤ 11.3
Áp dụng thuật toán trên cho đồ thị (nét mảnh) ta nhận
được cây bao trùm (nét đậm) như sau:
8
Hình 11.5. Cây bao trùm của đồ thị tìm theo
phương pháp duyệt theo chiều sâu
11.3. THUẬT TOÁN TÌM CÂY BAO TRÙM (tiếp)
Thuật toán 11.2 (Tìm cây bao trùm bằng phương pháp duyệt theo chiều rộng)
Dữ liệu: Biểu diễn mảng DK các danh sách kề của
đồ thị vô hướng G.
Kết quả: Cây bao trùm (V, T) của đồ thị G.
11.3. THUẬT TOÁN TÌM CÂY BAO TRÙM (tiếp)
Thuật toán
1 BEGIN
2 for u  V do Duyet [u] := false ;
3 T :=  ;
4 Q :=  ;
enqueue z into Q ; { z là đỉnh tuỳ ý của
đồ thị và là gốc của cây }
6 Duyet [z] := true ;
11.3.THUẬT TOÁN TÌM CÂY BAO TRÙM (tiếp)
7 while Q   do
8 begin deqưeue v from Q ;
9 for u  DK[v] do
10 if ! Duyet [u] then
11 begin enqueue u into Q ;
12 Duyet [u] := true ;
13 T := T  {(v, u)} end
14 end
END.
11.3. THUẬT TOÁN TÌM CÂY BAO TRÙM (tiếp)
Độ phức tạp của thuật toán: O(m+n).
Ví dụ: Áp dụng thuật toán trên cho đồ thị (nét mảnh) ta
nhận được cây bao trùm (nét đậm) như sau:
Hình 11.6. Cây bao trùm của đồ thị tìm theo
phương pháp duyệt theo chiều rộng