BÀI 18
Chương 11
Cây và một số ứng dụng

Trong chương này ta xét một dạng đặc biệt nhưng có nhiều ứng dụng của đồ
thị vô hướng. Đó là khái niệm cây.

11.1. Cây Khái niệm cây được Cayley đưa ra đầu tiên vào năm 1857.

Định nghĩa 11.1: Giả sử T = (V, E) là đồ thị vô hướng. Ta nói rằng đồ thị T là
một cây nếu nó liên thông và không có chu trình.

Ví dụ 11.2: Đồ thị dưới đây là một cây.
Hình 11.1. Cây 7 đỉnh

Kết quả dưới đây sẽ cho chúng ta một số tính chất lý thú và có thể dùng làm
định nghĩa cho cây.

Định lý 11.1. Với đồ thị vô hướng T có số đỉnh không ít hơn 2, các tính chất sau
đây 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 nối hai đỉnh bất kỳ không kề
nhau thì xuất hiện một chu trình.

11.2. Cây bao trùm của đồ thị

Giả sử G là một đồ thị vô hướng.

11.2.1. Cây bao trùm

Định nghĩa 11.3: 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.4: Đồ thị G được cho như hình vẽ dưới đây.
Hình 11.2. Đồ thị có cây bao trùm

và một số cây bao trùm của G là:
Hình 11.3. Hai cây bao trùm của đồ thị trên

Cây bao trùm có nhiều ứng dụng trong các bài toán điều khiển giao thông, nối
các mạng điện …

Định lý 11.2: Đồ thị vô hướng G có cây bao trùm khi và chỉ khi 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à độ dài của đường đi ngắn nhất nối đỉnh a với đỉnh x.
Lần lượt xây dựng các tập hợp

Định lý 11.3 (Cayley): Số cây bao trùm của đồ thị vô hướng đầy đủ n đỉnh là n
n-2
.

Kết quả trên cho ta thấy số lượng cây bao trùm của một đồ thị nói chung là
rất lớn.

Các thuật toán duyệt đồ thị theo chiều rộng và chiều sâu là những công cụ tốt
để tìm cây bao trùm của đồ thị liên thông.

Thuật toán 11.4 (Tìm cây bao trùm của đồ thị liên thông 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.

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 ;

8 BEGIN { Chương trình chính }
9 for u ∈ V do Duyet [u] := false ;
10 T := ∅ ;
11 CBT_S (z) ; { z là đỉnh tuỳ ý của đồ thị, sẽ trở thành gốc của cây }
12 END.


4 Q := ∅ ;
5 enqueue z into Q ; { z là đỉnh tuỳ ý của đồ thị và là gốc của cây }
6 Duyet [z] := true ;
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)}
14 end
15 END.

Hiển nhiên, độ phức tạp của thật toán là: O(n+m)
Ví dụ 11.6: á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 rộng