Bài giảng Cây bao trùm

Khái niệm Cây bao trùmCho đồ thị G =(X,U). Giả sử G’ là đồ thị bộ phận của G. Nếu G’ =(X,U’) là một cây thì G’ gọi là cây bao trùm của đồ thị G.Cây bao trùm (tiếp)12345Cây bao trùm (tiếp)12345Cây bao trùm (tiếp)12345Cây bao trùm (tiếp)12345Cây bao trùm (tiếp)12345Cây bao trùm ngắn nhấtCho đồ thị G =(X,U). Mỗi cạnh (x,y) thuộc U có trọng số c(u,v) >= 0G’ = (X,U’) là cây bao trùm của GĐộ dài của cây G’ được xem là tổng trọng số của các cạnh tạo thành G’Tìm G’ của G sao cho G’ có độ dài ngắn nhấtThuật toán PrimCho G =(X,U) là đồ thi mà mỗi cạnh u thuộc U có trong số l(u)>=0Xác định cạnh có trọng số bé nhất trong tất cả các cạnh trong U. Giả sử là u1Giả sử u2 là cạnh có trọng số bé nhất trong các cạnh U \ {u1}Giả sử u3 là cạnh có trọng số bé nhất trong các cạnh U \{u1,u2}. Với điều kiện {u1,u2,u3} không tạo thành chu trìnhThuật toán Prim (tiếp).Giả sử bước k ta đã xác định được {u1,u2,u3,,uk} có trọng số bé nhất và không tạo thành chu trìnhThực hiện bước n-1 thì dừng lại. Khi đó ta có {u1,u2,u3,,un-1} không tạo thành chu trình và có trọng số bé nhất. Khi đó ta có G’ =(X,Un-1) là cây bao trùm bé nhất của G cần tìmThuật toán Prim (tiếp)123546176284353912354612353Thuật toán Prim (tiếp)Cho đồ thị G = (X,U)Gọi X’ là tập các đỉnh kề các cạnh trong G’Ban đầu X chứa một đỉnh tuỳ ý trong G giả sử x, tập các cạnh G’ rỗngỞ mỗi bước ta chọn cạnh (x,y) ngắn nhất sao cho x X’ và y  X-X’. Thêm y vào X’ và thêm (x,y) vào G’Tiếp tục phát triển G’ cho đến khi X’ =X. Khi đó G’ trở thành cây bao trùm ngắn nhất của GThuật toán Prim (tiếp)X ={x} (x: đỉnh tuỳ ý thuộc X)G =Thực hiện các bước sau cho đến khi X’=XChọn cạnh (x,y) có trọng số nhỏ nhất với x  X’, y  X-X’X’ = X’  {x}G’ =G’  {(x,y) }Thuật toán Prim (tiếp)1235461762843539BướcX’(x,y)Khởi tạo{1}-1{1,4}(1,4)2{1,4, 5}(1,5)3{1,4, 5, 3}(5,3)4{1,4, 5, 3, 2}(3, 2)5{1,4, 5, 3, 2, 6}(3, 6)Thuật toán Prim (tiếp)1235461762843539BướcX’(x,y)Khởi tạo{3}-1{3, 2}(3, 2)2{3, 2, 6}(3, 6)3{3, 2, 6,5}(3, 5)4{3, 2, 6, 5, 1}(5, 1)5{3, 2, 6, 5, 1, 4}(1,4)Thuật toán Prim (tiếp)- Bài tập312356135461Tìm cây bao trùm ngắn nhất của đồ thị GThuật toán Prim (tiếp)- Bài tậpTìm cây bao trùm ngắn nhất của đồ thị Gabcdefghiklm2311122333333444