Bài giảng Lý thuyết đồ thị - Chương 4: Bài toán cây khung nhỏ nhất

Chương 4Bài toán cây khung nhỏ nhấtThe Minimum Spanning Tree Problem2Nội dung4.1. Cây và các tính chất cơ bản của cây4.2. Cây khung của đồ thị4.3. Xây dựng tập các chu trình cơ bản của đồ thị4.4. Bài toán cây khung nhỏ nhất3Cây và rừng (Tree and Forest)§Þnh nghÜa 1. Ta gäi c©y lµ ®å thÞ v« h­íng liªn th«ng kh«ng cã chu tr×nh. §å thÞ kh«ng cã chu tr×nh ®­îc gäi lµ rõng.Nh­ vËy, rõng lµ ®å thÞ mµ mçi thµnh phÇn liªn th«ng cña nã lµ mét c©y. T1T3Rừng F gồm 3 cây T1, T2,, T3T24VÍ DỤG1, G2 là câyG3, G4 không là cây5Các tính chất cơ bản của câyĐịnh lý 1. Giả sử T=(V,E) là đồ thị vô hướng n đỉnh. Khi đó các mệnh đề sau đây là tương đương: (1) T là liên thông và không chứa chu trình; (2) T không chứa chu trình và có n-1 cạnh; (3) T liên thông và có n-1 cạnh; (4) T liên thông và mỗi cạnh của nó đều là cầu; (5) Hai đỉnh bất kỳ của T được nối với nhau bởi đúng một đường đi đơn; (6) T không chứa chu trình nhưng hễ cứ thêm vào nó một cạnh ta thu được đúng một chu trình.6Nội dung4.1. Cây và các tính chất cơ bản của cây4.2. Cây khung của đồ thị4.3. Xây dựng tập các chu trình cơ bản của đồ thị4.4. Bài toán cây khung nhỏ nhất7Cây khung của đồ thịĐịnh nghĩa 2. Giả sử G=(V,E) là đồ thị vô hướng liên thông. Cây T=(V,F) với F E được gọi là cây khung của đồ thị G. abecdabecdabecdGĐồ thị G và 2 cây khung T1 và T2 của nóT2T18Số lượng cây khung của đồ thịĐịnh lý sau đây cho biết số lượng cây khung của đồ thị đầy đủ Kn:Định lý 2 (Cayley). Số cây khung của đồ thị Kn là nn-2 .abcabcbcacabK3Ba cây khung của K3Arthur Cayley(1821 – 1895)9Bài toán trong hoá học hữu cơBiểu diễn cấu trúc phân tử:Mỗi đỉnh tương ứng với một nguyên tửCạnh – thể hiện liên kết giữa các nguyên tửBài toán: Đếm số đồng phân của cacbua hydro no chứa một số nguyên tử cácbon cho trước10CHHHHCHHHHCHHCHHHHCHHCHHCHHHHCHHCHHCHHmethaneethanepropanebutane saturated hydrocarbons CnH2n+211Nội dung4.1. Cây và các tính chất cơ bản của cây4.2. Cây khung của đồ thị4.3. Xây dựng tập các chu trình cơ bản của đồ thị4.4. Bài toán cây khung nhỏ nhất12Tập các chu trình cơ bảnGi¶ sö G = (V, E) lµ ®¬n ®å thÞ v« h­íng liªn th«ng, H=(V,T) lµ c©y khung cña nã. C¸c c¹nh cña ®å thÞ thuéc c©y khung ta sÏ gäi lµ c¸c c¹nh trong, cßn c¸c c¹nh cßn l¹i sÏ gäi lµ c¹nh ngoµi.§Þnh nghÜa 3. NÕu thªm mét c¹nh ngoµi e  E \ T vµo c©y khung H chóng ta sÏ thu ®­îc ®óng mét chu tr×nh trong H, ký hiÖu chu tr×nh nµy lµ Ce . TËp c¸c chu tr×nh  = { Ce : e  E \ T } ®­îc gäi lµ tËp c¸c chu tr×nh c¬ b¶n cña ®å thÞ G.13Tính chấtGi¶ sö A vµ B lµ hai tËp hîp, ta ®­a vµo phÐp to¸n sau A  B = (A  B) \ (A  B). TËp AB ®­îc gäi lµ hiÖu ®èi xøng cña hai tËp A vµ B.Tªn gäi chu tr×nh c¬ b¶n g¾n liÒn víi sù kiÖn chØ ra trong ®Þnh lý sau ®©y:§Þnh lý 3. Gi¶ sö G=(V,E) lµ ®å thÞ v« h­íng liªn th«ng, H=(V,T) lµ c©y khung cña nã. Khi ®ã mäi chu tr×nh cña ®å thÞ G ®Òu cã thÓ biÓu diÔn nh­ lµ hiÖu ®èi xøng cña mét sè c¸c chu tr×nh c¬ b¶n.14Ý nghĩa ứng dụngViệc tìm tập các chu trình cơ bản giữ một vai trò quan trọng trong vấn đề giải tích mạng điện:Theo mỗi chu trình cơ bản của đồ thị tương ứng với mạng điện cần phân tích ta sẽ thiết lập được một phương trình tuyến tính theo định luật Kirchoff: Tổng hiệu điện thế dọc theo một mạch vòng là bằng không. Hệ thống phương trình tuyến tính thu được cho phép tính toán hiệu điện thế trên mọi đoạn đường dây của lưới điện. 15Thuật toán xây dựng tập chu trình cơ bảnĐầu vào: Đồ thị G=(V,E) ®­îc m« t¶ b»ng danh s¸ch kÒ Ke(v), vV.procedure Cycle(v);(* Tìm tập các chu trình cơ bản của thành phần liên thông chứa đỉnh vC¸c biÕn d, num, STACK, Index lµ toµn côc *)begin d:=d+1; STACK[d] := v; num := num+1; Index[v] := num; for u  Ke(v) do if Index[u]=0 then Cycle(u) else if (u  STACK[d-1]) and (Index[v] > Index[u]) then ; d := d-1;end;16Thuật toán xây dựng tập chu trình cơ bản(* Main Program *)BEGIN for v  V do Index[v] := 0; num := 0; d := 0; STACK[0] := 0; for v  V do if Index[v] = 0 then Cycle(v);END. Độ phức tạp: O(|V|+|E|)17Nội dung4.1. Cây và các tính chất cơ bản của cây4.2. Cây khung của đồ thị4.3. Xây dựng tập các chu trình cơ bản của đồ thị4.4. Bài toán cây khung nhỏ nhất18BÀI TOÁN CÂY KHUNG NHỎ NHẤTMinimum Spanning Tree (MST)19Bài toán CKNNBài toán: Cho đồ thị vô hướng liên thông G=(V,E) với trọng số c(e), e  E. Độ dài của cây khung là tổng trọng số trên các cạnh của nó. Cần tìm cây khung có độ dài nhỏ nhất. 1fdabceg27574134452Độ dài của cây khung là Tổng độ dài các cạnh: 1420Bài toán cây khung nhỏ nhấtCó thể phát biểu dưới dạng bài toán tối ưu tổ hợp: Tìm cực tiểu c(H) =  c(e)  min, eT với điều kiện H=(V,T) là cây khung của G.Do số lượng cây khung của G là rất lớn (xem định lý Cayley), nên không thể giải nhờ duyệt toàn bộ21Ứng dụng thực tế: Mạng truyền thôngCông ty truyền thông AT&T cần xây dựng mạng truyền thông kết nối n khách hàng. Chi phí thực hiện kênh nối i và j là cij. Hỏi chi phí nhỏ nhất để thực hiện việc kết nối tất cả các khách hàng là bao nhiêu?16375894210Giả thiết là: Chỉ có cách kết nối duy nhất là đặt kênh nối trực tiếp giữa hai nút.22Bµi to¸n x©y dùng hÖ thèng ®­êng s¾tGiả sử ta muốn xây dựng một hệ thống đường sắt nối n thành phố sao cho hành khách có thể đi lại giữa hai thành phố bất kỳ đồng thời tổng chi phí xây dựng phải là nhỏ nhất. Rõ ràng là đồ thị mà đỉnh là các thành phố còn các cạnh là các tuyến đường sắt nối các thành phố tương ứng với phương án xây dựng tối ưu phải là cây. Vì vậy, bài toán đặt ra dẫn về bài toán tìm cây khung nhỏ nhất trên đồ thị đầy đủ n đỉnh, mỗi đỉnh tương ứng với một thành phố, với độ dài trên các cạnh chính là chi phí xây dựng đường ray nối hai thành phố tương ứng Chó ý: Trong bµi to¸n nµy ta gi¶ thiÕt lµ kh«ng ®­îc x©y dùng tuyÕn ®­êng s¾t cã c¸c nhµ ga ph©n tuyÕn n»m ngoµi c¸c thµnh phè. 23Sơ đồ chung của các giải thuậtGeneric-MST(G, c) A = { } //Bất biến: A là tập con các cạnh của CKNN nào đó while A chưa là cây khung do tìm cạnh (u, v) là an toàn đối với A A = A {(u, v)} // A vẫn là tập con các cạnh của CKNN nào đó return A Tìm cạnh an toàn bằng cách nào? Cạnh rẻ nhấtđể đảm bảo tính bất biến24Lát cắtTa gọi lát cắt (S, V S) là một cách phân hoạch tập đỉnh V ra thành hai tập S và V S. Ta nói cạnh e là cạnh vượt lát cắt (S, V S) nếu một đầu mút của nó là thuộc S còn đầu mút còn lại thuộc V S. Giả sử A là một tập con các cạnh của đồ thị. Lát cắt (S,V S) được gọi là tương thích với A nếu như không có cạnh nào thuộc A là cạnh vượt lát cắt. 25Lát cắtLát cắt của G = (V, E) là phân hoạch V thành (S, V – S). Ví dụ. S = {a, b, c, f}, V – S = {e, d, g}Các cạnh (b, d), (a, d), (b, e), (c, e) là cạnh vượt lát cắt.Các cạnh còn lại không vượt lát cắt. fdabceg27571413445226Lát cắt tương thích với tập cạnhfdabceg27571413445Ví dụ. S = {a, b, c, f}A = { (a, b), (d, g), (f, b), (a, f) }A = A  { (b, d) }2121Lát cắt (S, V – S) là tương thích với A1 không tương thích với A2 (cạnh (b, d) vượt lát cắt). 27Cạnh nhẹfdabceg27571413445VD. S = {a, b, c, f}Cạnh (b, e) có trọng số 3, “nhẹ hơn” các cạnh vượt lát cắt còn lại (a, d), (b, d), và (c, e). cạnh nhẹCạnh nhẹ là cạnh có trọng số nhỏ nhất trong số các cạnh vượt lát cắt. 228Cạnh nhẹ là cạnh an toàn!Định lý. Giả sử (S, V – S) là lát cắt của G=(V, E) tương thích với tập con A của E, và A là tập con của tập cạnh của CKNN của G. Gọi (u, v) là cạnh nhẹ vượt lát cắt (S, V – S). Khi đó (u, v) là an toàn đối với A; nghĩa là, A  {(u, v)} cũng vẫn là tập con của tập cạnh của CKNN. SV – S426u vA gồm các cạnh đỏ. 229Tại sao cạnh nhẹ là an toàn?SV – S426u v2AyxA  { (u, v) }  T ', tức là, (u, v) là an toàn đối với A. Chứng minh. Giả sử T là CKNN (gồm các cạnh đỏ) chứa A.Giả sử cạnh nhẹ (u, v)  T. Ta có T  { (u, v) } chứa chu trình. Tìm được cạnh (x, y)  T vượt lát cắt (S, V – S). Cây khung T ' = T – { (x, y) }  { (u, v) } có độ dài  độ dài của cây khung T. Suy ra T ' cũng là CKNN.30 Hệ quả Giả sử A là tập con của E và cũng là tập con của tập cạnh của CKNN nào đó của G, và C là một thành phần liên thông trong rừng F = (V, A). Nếu (u, v) là cạnh nhẹ nối C với một thành phần liên thông khác trong F, thì (u, v) là an toàn đối với A.uvC74wCM Cạnh (u, v) là cạnh nhẹ vượt lát cắt (C, V – C) tương thích với A. Theo định lý trên, cạnh (u, v) là an toàn đối với A. A gồm 5 cạnh đỏ. 8Hệ quả31Tìm cạnh an toàn?Giả sử A là tập con của tập cạnh của một CKNN nào đó. A là rừng.Cạnh an toàn được bổ sung vào A có trọng số nhỏ nhấttrong số các cạnh nối các cặp thành phần liên thông của nó. Thuật toán KruskalThuật toán PrimA là cây. Cạnh an toàn là cạnh nhẹ nối đỉnh trong A với một đỉnh không ở trong A. Thuật toán Kruskal Thuật toán Kruskal32Generic-MST(G, c) A = { } //Bất biến: A là tập con các cạnh của CKNN nào đó while A chưa là cây khung do tìm cạnh (u, v) là an toàn đối với A A = A {(u, v)} // A vẫn là tập con các cạnh của CKNN nào đó return A A là rừng.Cạnh an toàn được bổ sung vào A có trọng số nhỏ nhấttrong số các cạnh nối các cặp thành phần liên thông của nó. 33Thuật toán Kruskal – Ví dụfdabceg275714134452Độ dài của CKNN: 1434Mô tả thuật toán Kruskalprocedure Kruskal;begin sắp xếp các cạnh e1, . . . , em theo thứ tự không giảm của độ dài; T = ; (* T – tập cạnh của CKNN *) for i = 1 to m do if T {ei} không chứa chu trình then T := T  {ei};end35Thời gian tínhBước 1. Sắp xếp dãy độ dài cạnh. O(m log n)Bước lặp: Xác định xem T  { ei } có chứa chu trình hay không?Có thể sử dụng DFS để kiểm tra với thời gian O(n).Tổng cộng: O(m log n + mn)36Cách cài đặt hiệu quảVấn đề đặt ra là:Khi cạnh ei=(j,k) được xét, ta cần biết có phải j và k thuộc hai thành phần liên thông (tplt) khác nhau hay không. Nếu đúng, thì cạnh này được bổ sung vào cây khung và nó sẽ nối tplt chứa j và tplt chứa k.Thực hiện điều này như thế nào cho đạt hiệu quả?37Mỗi tplt C của rừng F được cất giữ như một tập.Ký hiệu First(C) đỉnh đầu tiên trong tplt C.Với mỗi đỉnh j trong tplt C, đặt First(j) = First(C) = đỉnh đầu tiên trong C.Chú ý: Thêm cạnh (i,j) vào rừng F tạo thành chu trình iff i và j thuộc cùng một tplt, tức là First(i) = First(j). Khi nối tplt C và D, sẽ nối tplt nhỏ hơn (ít đỉnh hơn) vào tplt lớn hơn (nhiều đỉnh hơn): Nếu |C| > |D|, thì First(CD) := First(C).Cách cài đặt hiệu quả38Phân tích thời gian tínhThời gian xác định First(i) = First(j) đối với i, j: O(1) cho mỗi cạnh. Tổng cộng là O(m).Thời gian nối 2 tplt S và Q, giả thiết |S|  |Q|.O(1) với mỗi đỉnh của Q (là tplt nhỏ hơn)Mỗi đỉnh i ở tplt nhỏ hơn nhiều nhất là log n lần. (Bởi vì, số đỉnh của tplt chứa i tăng lên gấp đôi sau mỗi lần nối.)Tổng cộng thời gian nối là: O(n log n).Tổng thời gian thực hiện thuật toán là: O( m log n + n log n).39Thuật toán PrimA là cây (Bắt đầu từ cây chỉ có 1 đỉnh) Cạnh an toàn là cạnh nhẹ nhất trong số các cạnh nối đỉnh trong A với một đỉnh không ở trong A.40fdabceg275714134452Thuật toán Prim – Ví dụcác cạnh để chọnchọng41fdabceg27571413445242fdabceg27571413445243fdabceg27571413445244fdabceg27571413445245fdabceg275714134452 Độ dài của CKNN: 14f46Mô tả thuật toán Primprocedure Prim(G, c)begin Chọn đỉnh tuỳ ý r V; Khởi tạo cây T=(V(T), E(T)) với V(T)={ r }và E(T)=; while T có c[u,v] then begin d[v] := c[u,v] ; near[v] := u; end; end; H = ( S , T ) lµ c©y khung nhá nhÊt cña ®å thÞ ;end; Thời gian tính: O(|V|2)49Thuật toán Prim – Ví dụVí dụ: Tìm CKNN cho đồ thị cho bởi ma trận trọng số 1 2 3 4 5 6 1 0 33 17    2 33 0 18 20   C = 3 17 18 0 16 4  4  20 16 0 9 8 5   4 9 0 14 6    8 14 0 50Thuật toán Prim: Ví dụBướcĐỉnh 1Đỉnh 2Đỉnh 3Đỉnh 4Đỉnh 5Đỉnh 6SKhởi tạo1234551Thuật toán Prim: Ví dụĐỉnh 1Đỉnh 2Đỉnh 3Đỉnh 4Đỉnh 5Đỉnh 6SKhởi tạo[0, 1][33, 1][17, 1]*[, 1][, 1][, 1]11234552Thuật toán Prim: Ví dụĐỉnh 1Đỉnh 2Đỉnh 3Đỉnh 4Đỉnh 5Đỉnh 6SKhởi tạo[0, 1][33, 1][17, 1]*[, 1][, 1][, 1]11 -[18, 3]-[16, 3][4, 3]*[, 1]1, 32345for v V\ S do if d[v] > c[u,v] then d[v] := c[u,v] ; near[v] := u;53Thuật toán Prim: Ví dụĐỉnh 1Đỉnh 2Đỉnh 3Đỉnh 4Đỉnh 5Đỉnh 6SKhởi tạo[0, 1][33, 1][17, 1]*[, 1][, 1][, 1]11 -[18, 3]-[16, 3][4, 3]*[, 1]1, 32 -[18, 3]-[9,5]*-[14, 5]1, 3, 5345for v V\ S do if d[v] > c[u,v] then d[v] := c[u,v] ; near[v] := u;54Thuật toán Prim: Ví dụĐỉnh 1Đỉnh 2Đỉnh 3Đỉnh 4Đỉnh 5Đỉnh 6SKhởi tạo[0, 1][33, 1][17, 1]*[, 1][, 1][, 1]11 -[18, 3]-[16, 3][4, 3]*[, 1]1, 32 -[18, 3]-[9,5]*-[14, 5]1, 3, 53-[18,3]---[8,4]*1,3,5,445for v V\ S do if d[v] > c[u,v] then d[v] := c[u,v] ; near[v] := u;55Thuật toán Prim: Ví dụĐỉnh 1Đỉnh 2Đỉnh 3Đỉnh 4Đỉnh 5Đỉnh 6SKhởi tạo[0, 1][33, 1][17, 1]*[, 1][, 1][, 1]11 -[18, 3]-[16, 3][4, 3]*[, 1]1, 32 -[18, 3]-[9,5]*-[14, 5]1, 3, 53-[18,3]---[8,4]*1,3,5,44-[18,3]*----1,3,5,4,65for v V\ S do if d[v] > c[u,v] then d[v] := c[u,v] ; near[v] := u;56Thuật toán Prim: Ví dụĐỉnh 1Đỉnh 2Đỉnh 3Đỉnh 4Đỉnh 5Đỉnh 6SKhởi tạo[0, 1][33, 1][17, 1]*[, 1][, 1][, 1]11 -[18, 3]-[16, 3][4, 3]*[, 1]1, 32 -[18, 3]-[9,5]*-[14, 5]1, 3, 53-[18,3]---[8,4]*1,3,5,44-[18,3]*----1,3,5,4,65------1,3,5,4,6,2Độ dài của CKNN : 18 + 17 + 9 + 4 + 8 = 56Tập cạnh của CKNN: {(2,3), (3,1), (4,5), (5,3), (6,4)} Người đề xuất bài toán MST57Otakar BorůvkaNhà khoa học Séc (Czech)Người đề xuất bài toánĐề xuất thuật toán thời gian O(m log n)Bài báo được xuất bản ở Séc từ năm 1926.Ứng dụng vào việc phát triển hệ thống mạng điện ở Bohemia.Tăng tốcO(m log n) Borůvka, Prim, Dijkstra, Kruskal,O(m log log n) Yao (1975), Cheriton-Tarjan (1976)O(m (m, n)) Fredman-Tarjan (1987)O(m log (m, n)) Gabow-Galil-Spencer-Tarjan (1986)O(m (m, n)) Chazelle (JACM 2000)Optimal Pettie-Ramachandran (JACM 2002)5859 Questions?60