Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 9 có nội dung trình bày về cây khung nhỏ nhất, định nghĩa cạnh an toàn, giải thuật tổng quát, phép cắt, định nghĩa cạnh nhẹ, giải thuật của Kruskal, và cách thực thi giải thuật của Kruskal, . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | Caây Khung Nhoû Nhaát Caây khung nhoû nhaát ª Cho moät ñoà thò lieân thoâng voâ höôùng G V E moät haøm troïng soá w E R ª Tìm moät taäp con khoâng chöùa chu trình T E noái taát caû caùc ñænh sao cho toång caùc troïng soá w T u v T w u v laø nhoû nhaát. Taäp T laøø moät caây vaø ñöôïc goïi laø moät caây khung nhoû nhaát. ª Baøi toaùn tìm caây khung nhoû nhaát baøi toaùn tìm T. Ch. 9 Cay khung nho nhat 2 Caây khung nhoû nhaát tieáp ª Giaûi baøi toaùn tìm caây khung nhoû nhaát Giaûi thuaät cuûa Kruskal Giaûi thuaät cuûa Prim. Ch. 9 Cay khung nho nhat 3 Caây khung nhoû nhaát ví duï 8 7 b c d 4 2 9 a 11 i 4 14 e 7 6 8 10 h g f 1 2 Taäp caùc caïnh xaùm laø moät caây khung nhoû nhaát Troïng soá toång coäng cuûa caây laø 37. Caây laø khoâng duy nhaát neáu thay caïnh b c baèng caïnh a h seõ ñöôïc moät caây khung khaùc cuõng coù troïng soá laø 37. Ch. 9 Cay khung nho nhat 4 Caïnh an toaøn ª Cho moät ñoà thò lieân thoâng voâ höôùng G V E vaø moät haøm troïng soá w E R. Tìm moät caây khung nhoû nhaát cho G ª Giaûi baøi toaùn baèng moät chieán löôïc greedy nuoâi moät caây khung lôùn daàn baèng caùch theâm vaøo caây töøng caïnh moät. ª Ñònh nghóa caïnh an toaøn Neáu A laø moät taäp con cuûa moät caây khung nhoû nhaát naøo ñoù neáu u v laø moät caïnh cuûa G sao cho taäp A u v vaãn coøn laø moät taäp con cuûa moät caây khung nhoû nhaát naøo ñoù thì u v laø moät caïnh an toaøn cho A. Ch. 9 Cay khung nho nhat 5 Moät giaûi thuaät toång quaùt generic ª Moät giaûi thuaät toång quaùt generic ñeå tìm moät caây khung nhoû nhaát Input moät ñoà thò lieân thoâng voâ höôùng G moät haøm troïng soá w treân caùc caïnh cuûa G Output Moät caây khung nhoû nhaát cho G. GENERIC-MST G w 1 A 2 while A khoâng laø moät caây khung nhoû nhaát 3 do tìm caïnh u v an toaøn cho A 4 A A u v 5 return A Ch. 9 Cay khung nho nhat 6 Pheùp caét Caùc khaùi nieäm quan troïng ª Moät pheùp caét S V S cuûa G V E laø moät phaân chia partition cuûa V. Ví duï S a b d e
