MỘT SỐ ỨNG DỤNG CỦA CÂY BAO TRÙM

11.4. MỘT SỐ ỨNG DỤNG
CỦA CÂY BAO TRÙM
Kiểm tra tính liên thông của một đồ thị: Đồ thị là liên thông  nó có cây bao trùm.
Xây dựng hệ cơ sở của các chu trình.
Giả sử đồ thị liên thông G = (V, E) với n đỉnh và m cạnh.
11.4. MỘT SỐ ỨNG DỤNG CỦA
CÂY BAO TRÙM (tiếp)
Thực hiện hai bước:
1. Xây dựng cây bao trùm T của G. Giả sử trong quá trình xây dựng cây bao trùm T ta đã bỏ đi các cạnh e1, e2, ... , em – n + 1
2. Xây dựng hệ chu trình cơ sở: Lần lượt thêm vào cây T các cạnh ei, khi đó sẽ xuất hiện chu trình αi - đây cũng là chu trình của đồ thị G. Sau đó lại xoá cạnh ei và thêm cạnh ei+1 vào. Cuối cùng ta nhận được các chu trình tương ứng là α1, α2, ..., αm – n + 1.
11.4. MỘT SỐ ỨNG DỤNG CỦA
CÂY BAO TRÙM (tiếp)
Hệ chu trình này độc lập vì:
 i  j thì i chứa ei nhưng không chứa ej, còn j
chứa ej nhưng không chứa ei.
Số các chu trình này là m - n +1 = m - n + p = c(G) = số
các chu trình độc lập cực đại.
Vậy hệ chu trình tìm được là một cơ sở của các chu trình trong đồ thị G.
VÍ DỤ 11.5
Xét đồ thị vô hướng:









n = 5, m = 8, p = 1. Vậy c(G) = 4.


Hình 11.7. Đồ thị và các cạnh bỏ đi
VÍ DỤ 11.5 (tiếp)
Một cây bao trùm T của G là:





Ta nhận được một hệ chu trình cơ sở:
α1 = [a, b, d] α3 = [a, b, c, d]
α2 = [a, b, e, d] α4 = [a, b, c, e, d]



11.5. CÂY BAO TRÙM NHỎ NHẤT
Bài toán: Cho đồ thị vô hướng G liên thông với tập cạnh E và hàm trọng số c : E  N. Tìm cây bao trùm T của G sao cho tổng trọng số của các cạnh của T đạt giá trị nhỏ nhất.

Một số thuật toán tìm cây bao trùm nhỏ nhất:
- Thuật toán Kruskal
- Thuật toán Prim
11.6. THUẬT TOÁN KRUSKAL
Thuật toán:
Chọn cạnh có trọng số bé nhất, ký hiệu là e1 và đặt W := {e1}.
Giả sử đã chọn được W = {e1, e2, ... , ei}. Chọn ei+1 là cạnh có trọng số bé nhất trong số các cạnh còn lại trong E W sao cho {e1, e2, ... , ei, ei+1} không chứa chu trình.
Bổ sung: W := W  {ei+1}.
Lặp lại các bước 2. – 3. chừng nào còn có thể.
11.6. THUẬT TOÁN KRUSKAL (tiếp)
Định lý 11.4 : Tập các cạnh W tìm được theo thuật toán Kruskal tạo nên cây bao trùm nhỏ nhất của đồ thị G.

Thuật toán Kruskal chi tiết
1 procedure Kruskal ;
2 begin
3 W :=  ; Z := E ;


11.6. THUẬT TOÁN KRUSKAL (tiếp)
4 while (|W| < n -1) and (Z  ) do
5 begin
6 chọn cạnh e có trọng số bé nhất trong Z ;
7 Z := Z {e} ;
8 if W  {e} không chứa chu trình then W := W  {e}
9 end ;
10 if |W| < n -1 then writeln(Đồ thị không liên
thông)
11 end ;
VÍ DỤ 11.6
Đồ thị có trọng số và cây bao trùm nhỏ nhất:
Hình 11.10. Đồ thị trọng số và một cây bao trùm nhỏ nhất
11.7. THUẬT TOÁN PRIM
Thuật toán Prim
Prim đã cải tiến thuật toán Kruskal như sau: ở mỗi
vòng lặp ta chọn cạnh có trọng số bé nhất trong số
các cạnh kề với các cạnh đã chọn mà không tạo nên
chu trình.

11.7. THUẬT TOÁN PRIM (tiếp)
Thuật toán Prim được gọi là phương pháp lân cận gần nhất: bắt đầu từ một đỉnh nào đó a của đồ thị G ta nối nó với đỉnh “gần” nhất, chẳng hạn b. Nghĩa là, cạnh (a, b) được chọn có trọng số bé nhất. Tiếp theo, trong số các cạnh kề với đỉnh a hoặc đỉnh b ta chọn cạnh có trọng số bé nhất mà không tạo nên chu trình với cạnh (a, b). Cạnh này dẫn đến đỉnh thứ ba c ...

Tiếp tục quá trình này cho đến khi nhận được cây gồm n đỉnh và n-1 cạnh. Đó chính là cây bao trùm nhỏ nhất.
11.7. THUẬT TOÁN PRIM (tiếp)
1 procedure Prim ;
2 begin
3 W := {cạnh có trọng số bé nhất };
4 for i := 1 to n - 2 do
5 begin
e := cạnh có trọng số bé nhất kề với cạnh
trong W và nếu ghép nó vào W thì không
tạo nên chu trình ;
W := W  {e}
end
9 end ;
CÂY BAO TRÙM NHỎ NHẤT (tiếp)
Định lý 11.5
Trong đồ thị vô hướng có trọng số đôi một khác
nhau, cây bao trùm nhỏ nhất tồn tại và duy nhất.
Chứng minh:
Vì trong vòng lặp chỉ có duy nhất một cạnh được
chọn. 

11.8. CÂY BAO TRÙM LỚN NHẤT
Trong các thuật toán Kruskal và Prim ta không ràng buộc về dấu của trọng số, nên có thể áp dụng cho đồ thị vô hướng với trọng số trên các cạnh có cùng dấu tuỳ ý.
11.8. CÂY BAO TRÙM LỚN NHẤT (tiếp)
Để tìm cây bao trùm lớn nhất ta có hai cách:
1. Đổi thành dấu - cho các trọng số trên các cạnh. áp dụng một trong hai thuật toán đã trình bày ở trên để tìm cây bao trùm nhỏ nhất. Sau đó đổi dấu + trở lại, ta sẽ được cây bao trùm lớn nhất.
2. Sửa đổi trong các thuật toán: bước “chọn cạnh có trọng số bé nhất ... “ được thay bằng “chọn cạnh có trọng số lớn nhất ... “ còn các bước khác thì giữ nguyên. Khi thuật toán kết thúc, ta sẽ nhận được cây bao trùm lớn nhất.