1
CHƯƠNG 11
CÂY VÀ MỘT SỐ ỨNG DỤNG
2
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
3
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.
4
VÍ DỤ 11.1
Đồ thị dưới đây là một cây.
ab
c
de
fg
Hình 11.1. Cây 7 đỉnh
5
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:
1. T là một cây.
2. T không có chu trình và có n- 1 cạnh.
3. T liên thông và có n- 1 cạnh.
4. 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.
5. 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.
6. Chỉ có duy nhất một đường đi nối hai đỉnh bất kỳ.