BÀI 19: Một số ứng dụng của cây bao trùm

Một số ứng dụng của cây bao trùm: 1) Kiểm tra tính liên thông của một đồ thị: Đồ thị là liên thông khi và chỉ khi nó có cây bao trùm. 2) Xây dựng hệ cơ sở của các chu trình. Trước hết, giả thiết rằng đồ thị liên thông G = (V, E) có n đỉnh và m cạnh. Trong trường hợp đồ thị không liên thông thì ta xét từng thành phần liên thông. Để xây dựng hệ cơ sở các chu trình thuộc G ta tiến hành hai bước sau đây: 1. Xây dựng cây...
Nội dung trích xuất từ tài liệu:
BÀI 19: Một số ứng dụng của cây bao trùm BÀI 1911.2.2. Một số ứng dụng của cây bao trùm1) Kiểm tra tính liên thông của một đồ thị: Đồ thị là liên thông khi và chỉ khi nócó cây bao trùm.2) Xây dựng hệ cơ sở của các chu trình. Trước hết, giả thiết rằng đồ thị liên thông G = (V, E) có n đỉnh và mcạnh. Trong trường hợp đồ thị không liên thông thì ta xét từng thành phần liênthông.Để xây dựng hệ cơ sở các chu trình thuộc G ta tiến hành hai bước sau đây: 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 (1 ≤ i ≤ m- n+1), nghĩa là khôi phục lại cạnhei trong G, 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.Ta nhận được các chu trình tương ứng: α1 , α2 , .. .. , αm-n+1.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ôngchứa ei.Hơn nữa, số các chu trình này là m - n +1 = m - n + p = chu số của G = số các chutrì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.7: Xét đồ thị vô hướng sau đây: Hình 11.7. Đồ thị và các cạnh bỏ điMột cây bao trùm T của G là: Hình 11.8. Một cây bao trùm của đồ thị trênTa nhận được một hệ chu trình cơ sở: α1 = [ a, b, d ] α2 = [ a, b, e, d ] α3 = [ a, b, c, d ] α4 = [ a, b, c, e, d ]. Cây bao trùm nhỏ nhất Bây giờ ta xét bài toán tổng quát tìm cây bao trùm.11.3.1. Bài toán cây bao trùm nhỏ nhất Cho đồ thị vô hướng G với tập cạnh E và hàm trọng số c : E → N. Hãy tìmcâ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. Chẳng hạn như, xây dựng một hệ thống đường dây tải điện từ trạm phát điệnđến các nơi tiêu thụ, nối các máy tính trong một mạng ... sao cho dây điện sử dụnglà ít nhất.11.3.2. Các thuật toán tìm cây bao trùm nhỏ nhất Giả sử G là một đồ thị vô hướng liên thông và có trọng số. Khi đó, đồ thị Gcó cây bao trùm và sẽ có cây bao trùm nhỏ nhất. Ta có thể dùng các thuật toán sau đây để tìm cây bao trùm nhỏ nhất của đồthị G.Thuật toán 11.6 ( Thuật toán Kruskal) 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ấttrong số các cạnh còn lại trong E W sao cho {e1, e2, ... , ei, ei+1} không chứa chutrình. Đặt W := W ∪{ei+1}. Lặp lại các bước 2) - 3) chừng nào còn có thể.Tập cạnh W nhận được ở vòng lặp cuối cùng sẽ cho ta cây bao trùm nhỏ nhất.Định lý 11.7: Tập các cạnh W tìm được theo thuật toán Kruskal là cây bao trùmnhỏ nhất của đồ thị G.Chứng minh: Để đơn giản chứng minh, ta xét hai trường hợp sau đây:i) Trước hết xét trường hợp G là đồ thị vô hướng đầy đủ có trọng số. Tập cạnh W không có chu trình, nhưng nếu thêm một cạnh bất kỳ giữa hai đỉnh(cạnh này luôn có) sẽ tạo nên chu trình vì nếu không có thì quá trình lặp chưa kếtthúc. Do đó theo tính chất 4) của cây, tập cạnh W là một cây. Mặt khác, mỗi đỉnh của đồ thị G đều kề với tập cạnh W vì nếu không thì còn cóthể thêm cạnh nữa vào W. Vậy trên W có n đỉnh và theo tính chất 3) của cây thìW có n -1 cạnh. Suy ra cây W là cây bao trùm của đồ thị G. Bây giờ ta sẽ chứng minh rằng, W là cây bao trùm nhỏ nhất của đồ thị G.Giả sử T là một cây bao trùm nhỏ nhất nào đó của G. Ký hiệu ei là cạnh đầu tiêncủa W không thuộc T, vậy thì: {e1, e2 , ... , ei-1} ⊆ T. Hình 11.9. Cách thay cạnh của T với WTheo tính chất 4) của cây, trong đồ thị T ∪{ei} có chu trình. Ký hiệu chu trình đólà H. Hiển nhiên, chu trình H phải chứa cạnh ei. H cũng không thể nằm trọntrong tập cạnh W vì trong W không có chu trình. Do vậy, có cạnh v trên chu trìnhnày thuộc T nhưng không thuộc W. Xét tập cạnh T’ = T {v}∪{ei}.- Tập cạnh T’ không thể có chu trình. Vì nếu nó chứa chu trình H’ nào đó thì H’phải chứa ei và không chứa v. Khi đó, tập cạnh (H’ {ei}) ∪ (H {ei}) sẽ là mộtchu trình và chu trình này phải nằm trong cây T, trái với tính chất 2) của cây.- Số cạnh của T’ là n-1. Vậy theo tính chất 2) của cây thì tập cạnh T’ là một cây vàlà cây bao trùm của đồ thị G.Hơn nữa, vì T là cây bao trùm nhỏ nhất nên: c(ei) ≥ c(v). Cạnh v không thể tạo vớitập cạnh W ở bước lặp i-1 để có chu trình vì W nằm trong T. Nhưng nếu c(ei) >c(v) thì trong bước lặp i ta đã không chọn cạnh ei. Vậy thì: c(ei) = c(v) và trọngsố của cây T bằng trọng số của cây T’. Ta nhận được cây bao trùm khác có trọng sốkhông đổi nhưng có thêm một cạnh chung với W là ei. Tiếp tục quá trình này ta sẽ nhận được cây bao trùm có trọng số bằng trọngsố của cây T và trùng với W. Suy ra, cây W cũng là cây bao trùm nhỏ nhất.ii) Bây giờ ta xét trường hợp G là đồ thị vô ...