Bài giảng Phân tích thiết kế giải thuật - Chương 9: Cây khung nhỏ nhất

Bài giảng Phân tích thiết kế giải thuật - Chương 9: Cây khung nhỏ nhất giới thiệu đến bạn đọc về những cách giải bài toán tìm cây khung nhỏ nhất, giải thuật tổng quát, thực thi giải thuật của Kruskal. Với các bạn đang học chuyên ngành Công nghệ thông tin thì đây là tài liệu tham khảo hữu ích dành cho các bạn.
Nội dung trích xuất từ tài liệu:
Bài giảng Phân tích thiết kế giải thuật - Chương 9: Cây khung nhỏ nhấtCâyKhungNhỏNhất Câykhungnhỏnhấtª Cho – mộtđồthịliênthông,vôhướngG=(V,E) – mộthàmtrọngsố w:E Rª TìmmộttậpconkhôngchứachutrìnhT Enốitấtcảcácđỉnhsao chotổngcáctrọngsố w(T)= (u,v) Tw(u,v)• lànhỏnhất. – TậpTlàømộtcây,vàđượcgọilàmộtcâykhungnhỏnhất.ª Bàitoántìmcâykhungnhỏnhất:bàitoántìmT.13.11.2004 Ch.9:Caykhungnhonhat 2 Câykhungnhỏnhất(tiếp)ª Giảibàitoántìmcâykhungnhỏnhất – GiảithuậtcủaKruskal – GiảithuậtcủaPrim.13.11.2004 Ch.9:Caykhungnhonhat 3 Câykhungnhỏnhất:vídụ 8 7 b c d 4 2 9 a 11 i 4 14 e 7 6 8 10 h g f 1 2 °Tậpcáccạnhxámlàmộtcâykhungnhỏnhất °Trọngsốtổngcộngcủacâylà37. °Câylàkhôngduynhất:nếuthaycạnh( b,c)bằngcạnh(a,h) sẽđượcmộtcâykhungkháccũngcótrọngsốlà37.13.11.2004 Ch.9:Caykhungnhonhat 4 Cạnhantoànª Chomộtđồthịliênthông,vôhướngG=(V,E)vàmộthàmtrọngsố w:E R.TìmmộtcâykhungnhỏnhấtchoG!ª Giảibàitoánbằngmộtchiếnlượcgreedy:nuôimộtcâykhunglớn dầnbằngcáchthêmvàocâytừngcạnhmột.ª Địnhnghĩacạnhantoàn NếuAlàmộttậpconcủamộtcâykhungnhỏnhấtnàođó,nếu(u,v) làmộtcạnhcủaGsaochotậpA {(u,v)}vẫncònlàmộttậpcon củamộtcâykhungnhỏnhấtnàođó,thì(u,v)làmộtcạnhantoàn choA.13.11.2004 Ch.9:Caykhungnhonhat 5 Mộtgiảithuậttổngquát(generic)ª Mộtgiảithuậttổngquát(generic)đểtìmmộtcâykhungnhỏnhất – Input:mộtđồthịliênthông,vôhướngG mộthàmtrọngsốwtrêncáccạnhcủaG – Output:MộtcâykhungnhỏnhấtchoG. GENERICMST(G,w) 1 A 2 whileAkhônglàmộtcâykhungnhỏnhất 3 dotìmcạnh(u,v)antoànchoA 4 A A {(u,v)} 5 returnA13.11.2004 Ch.9:Caykhungnhonhat 6 Phépcắt Cáckháiniệmquantrọngª Mộtphépcắt(S,V S)củaG=(V,E)làmộtphânchia(partition) củaV. Vídụ:S={a,b,d,e}trongđồthịsau.ª Mộtcạnh(u,v) Exuyênqua(cross)mộtphépcắt(S,V S)nếu mộtđỉnhcủanónằmtrongSvàđỉnhkianằmtrongV S. Vídụ:cạnh(b,c). 8 7 b c d 4 2 9 a 11 i 4 14 e S 7 6 10 8 V S h g f 1 213.11.2004 Ch.9:Caykhungnhonhat 7 Cạnhnhẹ(lightedge) Cáckháiniệmquantrọng(tiếp)ª MộtphépcắtbảotoàntậpcáccạnhA(respectsA)nếukhôngcó cạnhnàocủaAxuyênquaphépcắt.ª Mộtcạnhlàmộtcạnhnhẹvượtquaphépcắtnếutrọngsốcủanólà nhỏnhấttrongmọitrọngsốcủacáccạnhxuyênquaphépcắt.Vídụ: cạnh(c,d). 8 7 b c d 4 2 9 a 11 i 4 e S 7 6 14 8 10 V S h g f 1 213.11.2004 Ch.9:Caykhungnhonhat 8 Nhậnramộtcạnhantoàn Địnhlý24.1 Cho ° G=(V,E)làmộtđồthịliên ...