Bài giảng Tin học - 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ÙMKiể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. 111.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.211.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. 3VÍ DỤ 11.5Xét đồ thị vô hướng:	n = 5, m = 8, p = 1. Vậy c(G) = 4.abcdeG = 1234Hình 11.7. Đồ thị và các cạnh bỏ đi4VÍ 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]abcde511.5. CÂY BAO TRÙM NHỎ NHẤTBà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 Prim611.6. THUẬT TOÁN KRUSKALThuậ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ể.711.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ết1 procedure Kruskal ;2 begin3 W :=  ; Z := E ;811.6. THUẬT TOÁN KRUSKAL (tiếp)	 4 while (|W| < n -1) and (Z  ) do5	 begin6	 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 ; 9VÍ DỤ 11.6Đồ thị có trọng số và cây bao trùm nhỏ nhất: 111224656511125Hình 11.10. Đồ thị trọng số và một cây bao trùm nhỏ nhất 1011.7. THUẬT TOÁN PRIM Thuật toán PrimPrim đã 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. 1111.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.1211.7. THUẬT TOÁN PRIM (tiếp) 1 procedure Prim ;2 begin3 W := {cạnh có trọng số bé nhất };4 for i := 1 to n - 2 do5 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 ;13CÂY BAO TRÙM NHỎ NHẤT (tiếp)Định lý 11.5Trong đồ thị vô hướng có trọng số đôi một khácnhau, 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. 1411.8. CÂY BAO TRÙM LỚN NHẤTTrong 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ỳ ý. 1511.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. 16