›
›

Bài giảng Toán rời rạc - Xếp hạng đồ thị - Trần Nguyễn Minh Thư

pdf 99 trang hapham 1140
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc - Xếp hạng đồ thị - Trần Nguyễn Minh Thư", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_toan_roi_rac_xep_hang_do_thi_tran_nguyen_minh_thu.pdf

Nội dung text: Bài giảng Toán rời rạc - Xếp hạng đồ thị - Trần Nguyễn Minh Thư

  1. 1 TRƯỜNG ĐẠI HỌC CẦN THƠ KHOA CNTT & TRUYỀN THÔNG BỘ MÔN KHOA HỌC MÁY TÍNH TOÁN RỜI RẠC (DISCRETE MATHEMATICS) 08/2013 GV: Trần Nguyễn Minh Thư (tnmthu@ctu.edu.vn)
  2. 2 XẾP HẠNG ĐỒ THỊ
  3. Sắp xếp tôpô (xếp hạng) Thứ tự tôpô của một đồ thị có hướng là một thứ tự sắp xếp của các đỉnh sao cho với mọi cung từ u đến v trong đồ thị, u luôn nằm trước v. Thuật toán để tìm thứ tự tôpô gọi là thuật toán sắp xếp tôpô. Thứ tự tôpô tồn tại khi và chỉ khi đồ thị không có chu trình. Đồ thị có hướng không có chu trình luôn có ít nhất một thứ tự tôpô, và có thuật toán để tìm thứ tự tô pô trong thời gian tuyến tính.
  4. Giải thuật xếp hạng 1)- Khởi tạo: là tập hợp các ảnh của i (các đỉnh đi từ i) i d i là số tạo ảnh của i (i X), (tổng số đỉnh đến i) k=0 Sk= {s} 2)- Với mỗi k thực hiện: Sk+1 =  Với mỗi i Sk thực hiện : r(i) = k Với mỗi j là ảnh của i (đỉnh đi từ i) thực hiện: d j d j 1 Nếu thì gán S = S + {j} d j 0 k+1 k+1 k = k+1 Nếu Sk =  thì giải thuật kết thúc, ngược lại thì quay về (2).
  5. Giải thuật xếp hạng 2 4 1 7 3 5 6
  6. Giải thuật xếp hạng 2 4  Khởi tạo: 1 7  s = 1 là đỉnh gốc  k = 0 3 5  S0 = {1} 6 i 1 2 3 4 5 6 7 i 2,3 4,5,6 2,5,6 7 7 4,5  di 0 2 1 2 3 2 2
  7. 2 4 i 1 2 3 4 5 6 7 1 7 i 2,3 4,5,6 2,5,6 7 7 4,5  3 5 6 di 0 21 10 2 3 2 2 1)- Với k= 0 thực hiện: r(r(ii)) 0 S1 =  Lần lượt xét các đỉnh i trong S0 ={1}:  i=1: r(1) = 0 Lần lượt xét các đỉnh j trong 1 = {2,3} j=2: d(2)=d(2)-1=2-1=1 j=3: d(3)=d(3)-1=1-1=0 nên S1 = S1 + {3} ={3} k= k+1= 0+1= 1 S1  nên quay về đầu vòng lặp.
  8. 2 4 i 1 2 3 4 5 6 7 1 7 i 2,3 4,5,6 2,5,6 7 7 4,5  3 5 6 di 0 10 0 2 32 21 2 2)- Với k= 1 thực hiện: r(i) 0 1 S2 =  Lần lượt xét các đỉnh i trong S1 = {3}:  i=3: r(3) = 1 Lần lượt xét các đỉnh j trong 3 = {2,5,6}: j=2: d(2)=d(2)-1=1-1=0 nên : S2 = S2 + {2} = {2} j=5: d(5)=d(5)-1=3-1=2 j=6: d(6)=d(6)-1=2-1=1 k=k+1=1+1=2 S2  nên quay về đầu vòng lặp. 8 Võ Trí Thức
  9. 2 4 i 1 2 3 4 5 6 7 1 7 i 2,3 4,5,6 2,5,6 7 7 4,5  3 5 6 di 0 0 0 21 21 10 2 3)Với k= 2 thực hiện: r(r(ii)) S3 =  0 2 1 Lần lượt xét các đỉnh i trong S2 = {2}:  i=2: r(2) = 2 Lần lượt xét các đỉnh j trong 2= {4,5,6}: j=4: d(4)=d(4)-1=2-1=1 j=5: d(5)=d(5)-1=2-1=1 j=6: d(6)=d(6)-1=1-1=0 nên S3 = S3 + {6} = {6} k=k+1=2+1=3 S3  nên quay về bước đầu vòng lặp.
  10. 2 4 i 1 2 3 4 5 6 7 1 7 i 2,3 4,5,6 2,5,6 7 7 4,5  3 5 6 di 0 0 0 10 10 0 2 4)- Với k= 3 thực hiện: r(i) S4 =  0 2 1 3 Lần lượt xét các đỉnh i trong S3 = {6}:  i=6 r(6)=3 Lần lượt xét các đỉnh j trong 6= {4,5}: j=4: d(4)=d(4)-1=1-1=0 nên S4 = S4 + {4} = {4} j=5: d(5)=d(5)-1=1-1=0 nên S4 = S4 + {5} = {4,5} k=k+1=3+1=4 S4  nên quay về đầu vòng lặp.
  11. 2 4 1 7 i 1 2 3 4 5 6 7 i 2,3 4,5,6 2,5,6 7 7 4,5  3 5 6 d 0 0 0 0 0 0 210 5)- Với k= 4 thực hiện: i S5 =  r(i) 0 2 1 4 4 3 Lần lượt xét các đỉnh i trong S4 = {4,5}:  i=4: r(4)=4 Lần lượt xét các đỉnh j trong 4= {7} j=7: d(7)=d(7)-1=2-1=1  i=5: r(5)=4 Lần lượt xét các đỉnh j trong 5= {7}: j=7: d(7)=d(7)-1=1-1=0 nên S5 = S5 + {7} = {7} k=k+1=4+1=5 S5  nên quay về đầu vòng lặp.
  12. 2 4 i 1 2 3 4 5 6 7 1 7 i 2,3 4,5,6 2,5,6 7 7 4,5  3 5 0 0 0 0 0 0 0 6 di 6)- Với k= 5 thực hiện: r(i) 0 2 1 4 4 3 5 S6 =  Lần lượt xét các đỉnh i trong S5 = {7}:  i=7: r(7)=5 Lần lượt xét các đỉnh j trong 7=  k=k+1=5+1=6 S6 = : giải thuật kết thúc.
  13. i 1 2 3 4 5 6 7 i 2,3 4,5,6 2,5,6 7 7 4,5  di 0 0 0 0 0 0 0 r(i) 0 2 1 4 4 3 5 4 1 3 2 6 7 5 S0 S1 S2 S3 S4 S5
  14. 2 4 i 1 2 3 4 5 6 7 1 7 i 2,3 4,5,6 2,5,6 7 7 4,5  3 5 0 0 0 0 0 0 0 6 di r(i) 0 2 1 4 4 3 5 4 1 3 2 6 7 5 S0 S1 S2 S3 S4 S5
  15. 2 4 i 1 2 3 4 5 6 7 1 7 i 2,3 4,5,6 2,5,6 7 7 4,5  3 5 0 0 0 0 0 0 0 6 di r(i) 0 2 1 4 4 3 5 4 1 3 2 6 7 5 S0 S1 S2 S3 S4 S5
  16. BÀI TẬP 16  Đề thi năm 2013 (Đợt 1) Phân hạng các đỉnh của đồ thị sau và vẽ đồ thị phân hạng 2 5 8 1 3 6 9 4 7
  17. BÀI TẬP 17  Đề thi năm 2013 (Đợt 1) 2 5 8 1 3 6 9 4 7 i 1 2 3 4 5 6 7 8 9 i 2, 3, 4 3, 5 9 3, 7 6, 8 3, 4, 7, 9 6, 9 d- 0 1 4 2 1 2 2 1 3
  18. BÀI TẬP 18  Đề thi năm 2013 (Đợt 1) i 1 2 3 4 5 6 7 8 9 i 2, 3, 4 3, 5 9 3, 7 6, 8 3, 4, 7, 9 6, 9 d- 0 0 3 1 1 2 2 1 3  Khởi tạo Gốc s = 1, k = 0, S0 = {s} Lặp 1 - S1 = {}, i = 1: r(1) = 0, j = 2: d (2) = 0, S1 = {2} j = 3: d-(3) = 3 j = 4: d-(4) = 1 k = 1
  19. BÀI TẬP 19  Đề thi năm 2013 (Đợt 1) i 1 2 3 4 5 6 7 8 9 i 2, 3, 4 3, 5 9 3, 7 6, 8 3, 4, 7, 9 6, 9 d- 0 0 2 1 0 2 2 1 3 Lặp 2 - S2 = {}, i = 2: r(2) = 1, j = 3: d (3) = 2 - j = 5: d (5) = 0, S2 = {5} k = 2
  20. BÀI TẬP 20  Đề thi năm 2013 (Đợt 1) i 1 2 3 4 5 6 7 8 9 i 2, 3, 4 3, 5 9 3, 7 6, 8 3, 4, 7, 9 6, 9 d- 0 0 2 1 0 1 2 0 3 Lặp 3 - S3 = {}, i = 5: r(5) = 2 j = 6: d (6) = 1 - j = 8: d (8) = 0, S3 = {8} k = 3
  21. BÀI TẬP 21  Đề thi năm 2013 (Đợt 1) i 1 2 3 4 5 6 7 8 9 i 2, 3, 4 3, 5 9 3, 7 6, 8 3, 4, 7, 9 6, 9 d- 0 0 2 1 0 0 2 0 2 - Lặp 4 S4 = {}, i = 8: r(8) = 3 j = 6: d (6) = 0, S4 = {6} j = 9: d-(9) = 2 k = 4
  22. BÀI TẬP 22  Đề thi năm 2013 (Đợt 1) i 1 2 3 4 5 6 7 8 9 i 2, 3, 4 3, 5 9 3, 7 6, 8 3, 4, 7, 9 6, 9 d- 0 0 1 0 0 0 1 0 1 - Lặp 5 S5 = {}, i = 6; r(6) = 4 j = 3: d (3) = 1 - j = 4: d (4) = 0, S5 = {4} j = 7: d-(7) = 1 j = 9: d-(9) = 1 k = 5
  23. BÀI TẬP 23  Đề thi năm 2013 (Đợt 1) i 1 2 3 4 5 6 7 8 9 i 2, 3, 4 3, 5 9 3, 7 6, 8 3, 4, 7, 9 6, 9 d- 0 0 0 0 0 0 0 0 1 Lặp 6 - S6 = {}, i = 4: r(4) = 5 j = 3: d (3) = 0, S6 = {3} - j = 7: d (7) = 0, S6 = {3, 7} k = 6
  24. BÀI TẬP 24  Đề thi năm 2013 (Đợt 1) i 1 2 3 4 5 6 7 8 9 i 2, 3, 4 3, 5 9 3, 7 6, 8 3, 4, 7, 9 6, 9 d- 0 0 0 0 0 0 0 0 0 Lặp 7 - S7 = {}, i = 3: r(3) = 6 j = 9: d (9) = 0, S7 = {9} i = 7 : r(7) = 6 k = 7
  25. BÀI TẬP 25  Đề thi năm 2013 (Đợt 1) 2 5 8 Lặp 8 1 3 6 9 S8 = {}, i = 9: r(9) = 7 S8 = {} thuật toán dừng 4 7 Đồ thị xếp hạng:  r(1) = 0 r(2) = 1  r(5) = 2 r(8) = 3  r(6) = 4 r(4) = 5  r(3) = 6 r(7) = 6  r(9) = 7
  26. BÀI TẬP 26 2 5 8 Đề thi năm 2013 (Đợt 1) 1 3 6 9 4 7 S S S S S S S 0 1 2 3 4 5 3 7 S 6 1 2 5 9 8 6 4 7
  27. BÀI TẬP 27  Đề thi năm 2013 (Đợt 2) Phân hạng các đỉnh của đồ thị sau và vẽ đồ thị phân hạng
  28. BÀI TẬP 28 i 1 2 3 4 5 6 7 8 9 i 2, 3, 4 3, 5, 8 6, 7, 9 3, 7 6, 9 7, 9 7, 9 d- 0 1 3 1 1 2 4 1 4
  29. BÀI TẬP 29 i 1 2 3 4 5 6 7 8 9 i 2, 3, 4 3, 5, 8 6, 7, 9 3, 7 6, 9 7, 9 7, 9 d- 0 0 2 0 1 2 4 1 4 Khởi tạo Gốc s = 1, k = 0, S0 = {s} Lặp 1. S1 = {}, i = 1: r(1) = 0, - j = 2: d (2) = 0, S1 = {2} j = 3: d-(3) = 2 - j = 4: d (4) = 0, S1 = {2, 4} k = 1
  30. BÀI TẬP 30 i 1 2 3 4 5 6 7 8 9 i 2, 3, 4 3, 5, 8 6, 7, 9 3, 7 6, 9 7, 9 7, 9 d- 0 0 0 0 0 2 3 0 4 Lặp 2: S2 = {}, i = 2: r(2) = 1, j = 3: d-(3) = 1 - j = 5: d (5) = 0, S2 = {5} j = 8: d-(8) = 0, S2 = {5, 8} i=4: r(4) = 1, j = 3: d-(3) = 0, S2 = {5, 8, 3} j = 7: d-(7) = 3 k = 2
  31. BÀI TẬP 31 i 1 2 3 4 5 6 7 8 9 i 2, 3, 4 3, 5, 8 6, 7, 9 3, 7 6, 9 7, 9 7, 9 d- 0 0 0 0 0 0 1 0 1 Lặp 3 S3 = {}, i = 5: r(5) = 2 j = 6: d-(6) = 1 j = 9: d-(9) = 3 i = 8: r(8) = 2 j = 7: d-(7) = 2 j = 9: d-(9) = 2 i = 3: r(3) = 2 - j = 6: d (6) = 0; S3 = {6} j = 7: d-(7) = 1 j = 9: d-(9) = 1
  32. BÀI TẬP 32 i 1 2 3 4 5 6 7 8 9 i 2, 3, 4 3, 5, 8 6, 7, 9 3, 7 6, 9 7, 9 7, 9 d- 0 0 0 0 0 0 0 0 0 Lặp 4 S4 = {}, i = 6: r(6) = 3 - j = 7: d (7) = 0, S4 = {7} - j = 9: d (9) = 0, S4 = {7, 9} k = 4
  33. BÀI TẬP 33 i 1 2 3 4 5 6 7 8 9 i 2, 3, 4 3, 5, 8 6, 7, 9 3, 7 6, 9 7, 9 7, 9 d- 0 0 0 0 0 0 0 0 0 Lặp 5 S5 = {}, i = 7: r(7) = 4 i = 9: r(9) = 4 Thuật toán dừng
  34. BÀI TẬP 34 S 0 S1 S2 S3 S4 5 2 9 1 3 6 4 8 7
  35. 35 Cây khung có trọng lượng nhỏ nhất XLNNTN - tnmtnhu@cit.ctu.edu.vn 8/2/2015
  36. Cây khung có trọng lượng nhỏ nhất 36  Cây:  Đồ thị vô hướng liên thông không có chu trình gọi là cây  Cây là một đồ thị vô hướng đơn Cây T
  37. 1.Giới thiệu về cây 2.Cây khung 3.Cây có hướng Các tính chất của Cây 4.BT Cây có hướng  Định lý 1:  J=(X,T) là đồ thị vô hướng  J là cây khi và chỉ khi tồn tại duy nhất một đường đi nối 2 đỉnh bất kỳ của J 37
  38. Các tính chất của Cây  Định lý 2:  J=(X,T) là đồ thị vô hướng với số đỉnh n 2  Các tính chất tương đương 1. J là cây 2. J không có chu trình và có n-1 cạnh 3. J liên thông và có n-1 cạnh. 4. J không có chu trình, nhưng nếu thêm một cạnh nối hai đỉnh bất kỳ không kề nhau thì xuất hiện chu trình. 5. J liên thông nhưng nếu bớt đi một cạnh bất kỳ thì sẽ làm mất đi tính liên thông. 6. Mỗi cặp đỉnh được nối với nhau bằng đúng một đường đi sơ cấp. 38
  39. Cây khung có trọng lượng nhỏ nhất Bài toán cây khung có trọng lượng nhỏ nhất  G=(X,U) là một đồ thị vô hướng  w(u): trọng số, với  u Є U  Cây khung (cây bao trùm) trên G là một đồ thị bộ phận liên thông không có chu trình   Đồ thị Cây khung Cây khung  Khi đồ thị vô hướng G có n đỉnh thì cây khung của G,nếu có, là một đồ thị liên thông có n đỉnh và n-1 cạnh  Một đồ thị có thể có rất nhiều cây khung khác nhau.  Bài toán tìm cây khung có tổng trọng số các cạnh là nhỏ nhất. 39
  40. Giải thuật Kruskal  G=(X,U) là một đồ thị vô hướng  Sắp xếp cạnh thứ tự theo trọng số tăng dần (Giải thuật Kruskal)  u1,u2,u3, ,um  Đọc lần lượt danh sách thứ tự các cạnh  Khởi đầu T={u1}.  Bước thứ k cạnh uk được đọc. Nếu T+{uk} không tạo thành chu trình thì thêm uk vào T  Chuyển sang cạnh tiếp theo đến hết các cạnh  Cây J=(X,T) là cây khung có trọng lượng nhỏ nhất   trọng lượng w(J) 40
  41. Cây khung có trọng lượng nhỏ nhất 4 1 2 1 9 5 12 10 6 7 5 2 7 3 6 11 4 3 8 41
  42. 1.Giới thiệu về cây 2.Cây khung 3.Cây có hướng Giải thuật Kruskal 4.BT Cây có hướng 4 1 2 1 9 5 12  G=(X,U) là một đồ thị vô hướng 6 7 10 5 2  7 Sắp xếp thứ tự các cạnh theo trọng 3 6 11 số tăng dần 4 3 8  (1,6), (6,7), (6,4), (1,2), (2,7), 4 (4,7), (3,7), (3,4), (2,5), (5,7), 1 2 1 9 5 (3,5), (1,7) 12 10  6 7 5 Khởi đầu 2 7  3 6 T={(1,6)} 11  4 3 w(J)=w(1,6)=1 8
  43. 1.Giới thiệu về cây 2.Cây khung 3.Cây có hướng Giải thuật Kruskal 4.BT Cây có hướng (1,6), (6,7), (6,4), (1,2), (2,7), (4,7), (3,7), (3,4), (2,5), (5,7), (3,5), (1,7) 4 1 2 1 9 5  Bước lặp, đọc lần lượt danh sách các 12 6 7 10 5 cạnh 2 7  1)- Với cạnh (6,7) 3 6 11  T{(6,7)} không tạo thành chu trình. 4 3 8 4  T= T {(6,7)} = {(1,6),(6,7)} 1 2 1 9  5 w(J)=w(J)+w(6,7)=1+2=3 12  2)- Với cạnh (6,4) 6 7 10 5 2  T{(6,4)} không tạo thành chu trình. 7 3 6 11  T= T {(6,4) } = {(1,6),(6,7),(6,4)} 4 3 8  w(J)=w(J)+w(6,4)=3+3=6
  44. Giải thuật Kruskal (1,6), (6,7), (6,4), (1,2), (2,7), (4,7), (3,7), (3,4), (2,5), (5,7), (3,5), (1,7) 4 1 2 1 9 5  3)- Với cạnh (1,2) 12  6 7 10 5 T{(1,2)} không tạo thành chu trình. 2 7  T=T{(1,2)} = 3 6 11 {(1,6),(6,7),(4,6),(1,2)} 4 3 8 4  w(J)=w(J)+w(1,2)=6+4=10 1 2 1 9  4)- Với cạnh (2,7) 5 12  T{(2,7)} tạo thành chu trình 6 7 10 5 2 7 3 6 11 4 3 8
  45. Giải thuật Kruskal (1,6), (6,7), (6,4), (1,2), (2,7), (4,7), (3,7), (3,4), (2,5), (5,7), (3,5), (1,7) 4 1 2 1 9 5  3)- Với cạnh (1,2) 12  T{(1,2)} không tạo thành chu trình6. 7 10 5 2 7  T=T{(1,2)} = 3 6 11 {(1,6),(6,7),(4,6),(1,2)} 4 3 8 4  w(J)=w(J)+w(1,2)=6+4=10 1 2 1 9  4)- Với cạnh (2,7) 5 12  T{(2,7)} tạo thành chu trình 6 7 10 5 2 7 3 6 11 4 3 8
  46. Giải thuật Kruskal (1,6), (6,7), (6,4), (1,2), (2,7), (4,7), (3,7), (3,4), (2,5), (5,7), (3,5), (1,7) 4 1 2 1 9 5  3)- Với cạnh (1,2) 12 6 7 10 5  T{(1,2)} không tạo thành chu trình. 2 7  T=T{(1,2)} = 3 6 11 {(1,6),(6,7),(4,6),(1,2)} 4 3 8 4  w(J)=w(J)+w(1,2)=6+4=10 1 2 1 9  4)- Với cạnh (2,7) 5 12  T{(2,7)} tạo thành chu trình 6 7 10 5 2  5)- Với cạnh (4,7) 7 3 6 11  T{(4,7)} tạo thành chu trình 4 3 8 46
  47. 1.Giới thiệu về cây 2.Cây khung 3.Cây có hướng Giải thuật Kruskal 4.BT Cây có hướng (1,6), (6,7), (6,4), (1,2), (2,7), (4,7), (3,7), (3,4), (2,5), (5,7), (3,5), (1,7) 4 1 2 1 9 5  3)- Với cạnh (1,2) 12  T{(1,2)} không tạo thành chu trình6. 7 10 5 2  7 T=T{(1,2)} = 3 6 11 {(1,6),(6,7),(4,6),(1,2)} 4 3 8  w(J)=w(J)+w(1,2)=6+4=10 4  4)- Với cạnh (2,7) 1 2 1 9 5  T{(2,7)} tạo thành chu trình 12 10  5)- Với cạnh (4,7) 6 7 5 2 7  T{(4,7)} tạo thành chu trình 3 6 11 4 3 8
  48. 1.Giới thiệu về cây 2.Cây khung 3.Cây có hướng 4.BT Cây có hướng Giải thuật Kruskal (1,6), (6,7), (6,4), (1,2), (2,7), (4,7), (3,7), (3,4), (2,5), (5,7), (3,5), (1,7) 4 1 2 1 9 5  6)- Với cạnh (3,7) 12 10  6 7 5 T{(3,7)} không tạo thành chu trình. 2 7  T= T  {(3,7)} = 3 6 11 {(1,6),(6,7),(4,6),(1,2),(3,7)} 4 3 8  w(J)=w(J)+w(3,7)=10+7=17 4 1 2  7)- Với cạnh (3,4) 1 9 5 12  T{(3,4)} tạo thành chu trình. 6 7 10 5 2 7 3 6 11 4 3 8
  49. 1.Giới thiệu về cây 2.Cây khung 3.Cây có hướng 4.BT Cây có hướng Giải thuật Kruskal (1,6), (6,7), (6,4), (1,2), (2,7), (4,7), (3,7), (3,4), (2,5), (5,7), (3,5), (1,7) 4 1 2 1 9 5  6)- Với cạnh (3,7) 12  T{(3,7)} không tạo thành chu trình6. 7 10 5 2  7 T= T  {(3,7)} = 3 6 11 {(1,6),(6,7),(4,6),(1,2),(3,7)} 4 3 8  w(J)=w(J)+w(3,7)=10+7=17 4 1 2  7)- Với cạnh (3,4) 1 9 5 12  T{(3,4)} tạo thành chu trình. 6 7 10 5 2 7 3 6 11 4 3 8
  50. 1.Giới thiệu về cây 2.Cây khung 3.Cây có hướng 4.BT Cây có hướng Giải thuật Kruskal 4 (1,6), (6,7), (6,4), (1,2), (2,7), (4,7), (3,7), (3,4), (2,5), (5,71 ), (3,5), (1,7)2 1 9 5 12  6)- Với cạnh (3,7) 6 7 10 5  T{(3,7)} không tạo thành chu trình. 2 7 3 6  T= T  {(3,7)} = 11 {(1,6),(6,7),(4,6),(1,2),(3,7)} 4 3 8  w(J)=w(J)+w(3,7)=10+7=17  7)- Với cạnh (3,4) 4 1 2 1 9  T{(3,4)} tạo thành chu trình. 5 12  8)- Với cạnh (2,5) 6 7 10 5  T{(2,5)} không tạo thành chu trình. 2 7 3 6  T=T{(2,5)} = 11 {(1,6),(6,7),(4,6),(1,2),(3,7),(2,5)} 4 3 8  w(J)=w(J)+w(2,5)=17+9=26
  51. Giải thuật Kruskal (1,6), (6,7), (6,4), (1,2), (2,7), (4,7), (3,7), (3,4), (2,5), (5,7), (3,5), (1,7) 4 1 2 1 9  9)- Với cạnh (5,7) 5 12  T{(5,7)} tạo thành chu trình. 6 7 10 5 2 7 3 6 11 4 3 8 4 1 2 1 9 5 12 6 7 10 5 2 7 3 6 11 4 3 8
  52. Giải thuật Kruskal (1,6), (6,7), (6,4), (1,2), (2,7), (4,7), (3,7), (3,4), (2,5), (5,7), (3,5), (1,7) 4 1 2 1 9  9)- Với cạnh (5,7) 5 12  T{(5,7)} tạo thành chu trình. 6 7 10 5 2 7 3 6 11 4 3 8 4 1 2 1 9 5 12 6 7 10 5 2 7 3 6 11 4 3 8
  53. Giải thuật Kruskal (1,6), (6,7), (6,4), (1,2), (2,7), (4,7), (3,7), (3,4), (2,5), (5,7), (3,5), (1,7) 4 1 2 1 9  9)- Với cạnh (5,7) 5 12  T{(5,7)} tạo thành chu trình. 6 7 10 5 2  10)- Với cạnh (3,5) 7 3 6 11  T{(3,5)} tạo thành chu trình. 4 3 8 4 1 2 1 9 5 12 6 7 10 5 2 7 3 6 11 4 3 8
  54. Giải thuật Kruskal (1,6), (6,7), (4,6), (1,2), (2,7), (4,7), (3,7), (3,4), (2,5), (5,7), (3,5), (1,7) 4 1 2  9)- Với cạnh (5,7) 1 9 5  T{(5,7)} tạo thành chu trình. 12 6 7 10 5  10)- Với cạnh (3,5) 2 7 3 6  T{(3,5)} tạo thành chu trình. 11 4 3 8 4 1 2 1 9 5 12 6 7 10 5 2 7 3 6 11 4 3 8
  55. Giải thuật Kruskal (1,6), (6,7), (4,6), (1,2), (2,7), (4,7), (3,7), (3,4), (2,5), (5,7), (3,5), (1,7) 4 1 2 1 9  9)- Với cạnh (5,7) 5 12  T{(5,7)} tạo thành chu trình. 6 7 10 5 2  10)- Với cạnh (3,5) 7 3 6 11  T{(3,5)} tạo thành chu trình. 4 3 8  11)- Với cạnh (1,7) 4  T{(1,7)} tạo thành chu trình. 1 2 1 9 5 12 6 7 10 5 2 7 3 6 11 4 3 8
  56. Giải thuật Kruskal (1,6), (6,7), (4,6), (1,2), (2,7), (4,7), (3,7), (3,4), (2,5), (5,7), (3,5), (1,7) 4 1 2 1 9  9)- Với cạnh (5,7) 5 12  T{(5,7)} tạo thành chu trình. 6 7 10 5 2  10)- Với cạnh (3,5) 7 3 6 11  T{(3,5)} tạo thành chu trình. 4 3 8  11)- Với cạnh (1,7) 4 1 2  T{(1,7)} tạo thành chu trình. 1 9 5 12 6 7 10 5 2 7 3 6 11 4 3 8 56
  57. Giải thuật Kruskal (1,6), (6,7), (4,6), (1,2), (2,7), (4,7), (3,7), (3,4), (2,5), (5,7), (3,5), (1,7) 4 1 2 1 9  9)- Với cạnh (5,7) 5 12  T{(5,7)} tạo thành chu trình. 6 7 10 5 2  10)- Với cạnh (3,5) 7 3 6 11  T{(3,5)} tạo thành chu trình. 4 3 8  11)- Với cạnh (1,7) 4  T{(1,7)} tạo thành chu trình. 1 2 1 9 5  Kết quả 12 10  6 7 5 T = 2 {(1,6),(6,7),(4,6),(1,2),(3,7),(2,5)} 7 3 6 11  Cây khung nhỏ nhất J trên đồ thị có 4 3 trọng lượng w(J)=26 là: 8
  58. Bài tập Đề thi 2012, lần 1 58  Tìm cây khung có trọng lượng nhỏ nhất trong đồ thị được cho bởi ma trận trọng số sau A B C D E F G H K A 1 1 1 B 9 2 8 C 6 2 D 1 5 4 3 E 2 F 9 3 G 9 H 7 K
  59. Bài tập Đề thi 2012, lần 1 59  G=(X,U) là một đồ thị vô hướng  Sắp xếp thứ tự các cạnh theo trọng số tăng dần  AB,AC,AK,DE,BH,CK,EF,DK,FH,DH,DF,CD,HK,BK, BG,FG,GH A B C D E F G H K  Khởi đầu A 1 1 1  T={(AB)} B 9 2 8 C 6 2  w(J)=w(AB)=1 D 1 5 4 3 E 2 F 9 3 G 9 H 7 K
  60. Bài tập Đề thi 2012, lần 1 60  G=(X,U) là một đồ thị vô hướng  Sắp xếp thứ tự các cạnh theo trọng số tăng dần  AB,AC,AK,DE,BH,CK,EF,DK,FH,DH,DF,CD,HK,BK, BG,FG,GH  Bước lặp, đọc lần lượt danh sách các cạnh  1)- Với cạnh (AC)  T{(AC)} không tạo thành chu trình.  T= T {(AC)} = {(AB),(AC)}  w(J)=w(J)+w(AC)=1+1=2
  61. Bài tập Đề thi 2012, lần 1 61  G=(X,U) là một đồ thị vô hướng  Sắp xếp thứ tự các cạnh theo trọng số tăng dần  AB,AC,AK,DE,BH,CK,EF,DK,FH,DH,DF,CD,HK,BK, BG,FG,GH  Bước lặp, đọc lần lượt danh sách các cạnh  2)- Với cạnh (AK)  T{(AK)} không tạo thành chu trình.  T= T {(AK)} = {(AB),(AC),(AK)}  w(J)=w(J)+w(AK)=2+1=3
  62. Bài tập Đề thi 2012, lần 1 62  G=(X,U) là một đồ thị vô hướng  Sắp xếp thứ tự các cạnh theo trọng số tăng dần  AB,AC,AK,DE,BH,CK,EF,DK,FH,DH,DF,CD,HK,BK, BG,FG,GH  Bước lặp, đọc lần lượt danh sách các cạnh  3)- Với cạnh (DE)  T{(DE)} không tạo thành chu trình.  T= T {(DE)} = {(AB),(AC),(AK),(DE)}  w(J)=w(J)+w(DE)=3+1=4
  63. Bài tập Đề thi 2012, lần 1 63  G=(X,U) là một đồ thị vô hướng  Sắp xếp thứ tự các cạnh theo trọng số tăng dần  AB,AC,AK,DE,BH,CK,EF,DK,FH,DH,DF,CD,HK,BK, BG,FG,GH  Bước lặp, đọc lần lượt danh sách các cạnh  4)- Với cạnh (BH)  T{(BH)} không tạo thành chu trình.  T= T {(BH)} = {(AB),(AC),(AK),(DE),(BH)}  w(J)=w(J)+w(BH)=4+2=6
  64. Bài tập Đề thi 2012, lần 1 64  G=(X,U) là một đồ thị vô hướng  Sắp xếp thứ tự các cạnh theo trọng số tăng dần  AB,AC,AK,DE,BH,CK,EF,DK,FH,DH,DF,CD,HK,BK, BG,FG,GH  Bước lặp, đọc lần lượt danh sách các cạnh  5)- Với cạnh (CK)  T{(CK)} tạo thành chu trình.  6)- Với cạnh (EF)  T{(EF)} không tạo thành chu trình.  T= T {(EF)} = {(AB),(AC),(AK),(DE),(BH),(EF)}  w(J)=w(J)+w(EF)=6+2=8
  65. Bài tập Đề thi 2012, lần 1 65  G=(X,U) là một đồ thị vô hướng  Sắp xếp thứ tự các cạnh theo trọng số tăng dần  AB,AC,AK,DE,BH,CK,EF,DK,FH,DH,DF,CD,HK,BK, BG,FG,GH  Bước lặp, đọc lần lượt danh sách các cạnh  7)- Với cạnh (DK)  T{(DK)} không tạo thành chu trình.  T= T {(DK)} = {(AB),(AC),(AK),(DE),(BH),(EF),(DK)}  w(J)=w(J)+w(DK)=8+3=11  8)- Với cạnh (FH)  T{(FH)} tạo thành chu trình.
  66. Bài tập Đề thi 2012, lần 1 66  G=(X,U) là một đồ thị vô hướng  Sắp xếp thứ tự các cạnh theo trọng số tăng dần  AB,AC,AK,DE,BH,CK,EF,DK,FH,DH,DF,CD,HK,BK, BG,FG,GH  Bước lặp, đọc lần lượt danh sách các cạnh  9)- Với cạnh (DH)  T{(DH)} tạo thành chu trình.  10)- Với cạnh (DF)  T{(DF)} tạo thành chu trình.  11)- Với cạnh (CD)  T{(CD)} tạo thành chu trình.
  67. Bài tập Đề thi 2012, lần 1 67  G=(X,U) là một đồ thị vô hướng  Sắp xếp thứ tự các cạnh theo trọng số tăng dần  AB,AC,AK,DE,BH,CK,EF,DK,FH,DH,DF,CD,HK,BK, BG,FG,GH  Bước lặp, đọc lần lượt danh sách các cạnh  12)- Với cạnh (HK)  T{(HK)} tạo thành chu trình.  13)- Với cạnh (BK)  T{(DF)} tạo thành chu trình.
  68. Bài tập Đề thi 2012, lần 1 68  G=(X,U) là một đồ thị vô hướng  Sắp xếp thứ tự các cạnh theo trọng số tăng dần  AB,AC,AK,DE,BH,CK,EF,DK,FH,DH,DF,CD,HK,BK,BG, FG,GH  Bước lặp, đọc lần lượt danh sách các cạnh  14)- Với cạnh (BG)  T{(BG)} không tạo thành chu trình.  T= T {(BG)} = {(AB),(AC),(AK),(DE),(BH),(EF),(DK),(BG)}  w(J)=w(J)+w(DK)=11+9 =20
  69. Bài tập Đề thi 2012, lần 1 69  G=(X,U) là một đồ thị vô hướng  Sắp xếp thứ tự các cạnh theo trọng số tăng dần  AB,AC,AK,DE,BH,CK,EF,DK,FH,DH,DF,CD,HK,BK,BG, FG,GH  Bước lặp, đọc lần lượt danh sách các cạnh  15)- Với cạnh (BG)  T{(FG)} tạo thành chu trình.  16)- Với cạnh (GH)  T{(GH)} tạo thành chu trình. => Cây có trọng lượng w(J)=20 với các cạnh AB,AC,AK,DE,BH, EF,DK,BG
  70. Bài tập Đề thi 2012, lần 1 70  Tìm cây khung có trọng lượng nhỏ nhất trong đồ thị được cho bởi ma trận trọng số sau GIẢI F E D K A C B H G Trọng lượng cây : 20
  71. Giải thuật Prim  Khởi tạo  s là đỉnh được chọn trước  S={s} T =  w(J) = 0  Giải thuật  while S X do {  M= { j kề của S}  for j M {  Tìm i S sao cho i gần j nhất  Gán nhãn cho đỉnh j : ((i,j) , w(i,j))  }endfor  Chọn đỉnh có nhãn (trọng số) nhỏ nhất có thể trong các đỉnh được gán nhãn v, khi thêm vào S không tạo ra chu trình: ((u, v), w(u, v))  Khi đó cập nhật  S= S+{v}  T= T+{(u,v)}  w(J) = w(J) + w(u,v)  }endwhile
  72. Giải thuật Prim  Khởi tạo 4 1 2  s= 1 1 9 5  S = {1} 12 10  T =  6 7 5 2  Các bước lặp 7 3 6 11  1)- Với S = {1} X thực hiện 4 3  Xác định M = {2, 6, 7}. Gán nhãn cho các 8 đỉnh trong M 4 1 2  2: ((1,2),4) 1 9 5  6: ((1,6),1) 12  nhãn nhỏ nhất 7: ((1,7),12) 6 7 10 5 2  Cập nhật: 7 3 6  S = S +{6} = {1,6} 11  T = T + {(1,6)}={(1,6)} 4 3 8  w(J) = 1
  73. 1.Giới thiệu về cây 2.Cây khung 3.Cây có hướng Bước 1) 4.BT Cây có hướng S = S +{6} = {1,6} Giải thuật Prim T = T + {(1,6)}={(1,6)} 4 w(J) = 1 1 2 1 9 5 12  2)- Với S = {1,6} X thực hiện 6 7 10 5  Xác định M={2, 4, 7}. Gán nhãn cho các đỉnh 2 7 trong M 3 6 11  2: ((1,2),4) 4 3  4: ((6,4),3) 8  7: ((6,7),2) nhãn nhỏ nhất 4 1 2  Cập nhật: 1 9 5  S =S +{7} = {1, 6, 7} 12  T =T +{(6,7)} = {(1,6),(6,7)} 6 7 10 5 2  w(J) = 1+2 = 3 7 3 6 11 4 3 8
  74. Bước 2) S =S +{7} = {1, 6, 7} T =T +{(6,7)} = {(1,6),(6,7)} Giải thuật Prim 4 w(J) = 1+2 = 3 1 2 1 9 5 12  3)- Với S = {1, 6, 7 } X thực hiện : 6 7 10 5  Xác định M = {2, 3, 4, 5}. Gán nhãn cho các 2 7 đỉnh trong M 3 6 11  2: ((1,2),4) 4 3  3: ((7,3),7) 8  4: ((6,4),3) nhãn nhỏ nhất 4  5: ((7,5),10) 1 2 1 9  Cập nhật: 5 12  S = S+{4} = {1, 6, 7, 4 } 6 7 10 5  T = T+{(4, 6)} = {(1,6),(6,7),(4,6)} 2 7  3 6 w(J) = 3+3 = 6 11 4 3 8
  75. Bước 3) S = S+{4} = {1, 6, 7, 4 } T = T+{(4, 6)} = {(1,6), (6,7), (4,6)} Giải thuật Prim w(J) = 3+3 = 6 4 1 2 1 9 5 12  4)- Với S = {1, 6, 7, 4 } X thực hiện : 6 7 10 5  Xác định M = {2, 3, 5}. Gán nhãn cho các 2 7 đỉnh trong M 3 6 11  nhãn nhỏ nhất 2: ((1,2),4) 4 3  3: ((7,3),7) 8  5: ((7,5),10) 4 1  Cập nhật: 2 1 9 5  S = S+{ 2 } = {1, 2, 6, 4, 7 } 12  T = T + {(1,2)} 6 7 10 5 2 = {(1,6), (6,7), (4,6), (1, 2)} 7 3 6  w(J) = 6+4 = 10 11 4 3 8
  76. Bước 4) S = S+{ 2 } = {1, 2, 6, 4, 7 } T = T + {(1,2)} = {(1,6), (6,7), Giải thuật Prim 4 (4,6), (1, 2)} 1 2 1 9 w(J) = 6+4 = 10 5 12 10  5)- Với S = {1, 6, 7 , 4 , 2 } X thực hiện : 6 7 5 2  Xác định M = {3, 5}. Gán nhãn cho các đỉnh 7 3 6 trong M 11 4 3  3: ((7,3),7) nhãn nhỏ nhất 8  5: ((2,5),9)  Cập nhật: 4  S = S+{3}= {1, 2, 3, 6, 4, 7} 1 2 1 9 5  T = T +{(7,3)} 12 = {(1,6), (6,7), (4,6), (1,2), (7,3)} 6 7 10 5 2  w(J) = 10+7 =17 7 3 6 11 4 3 8 76
  77. Bước 5) S = S+{3}= {1, 2, 3, 6, 4, 7} T = T +{(7,3)} = {(1,6), (6,7), Giải thuật Prim (4,6), (1,2), (7,3)} 4 w(J) = 10+7 =17 1 2 1 9 5 12  6)- Với S = {1, 6, 7 , 4 , 2 , 3} X thực hiện : 6 7 10 5  Xác định M = {5}. Gán nhãn cho các đỉnh 2 7 trong M 3 6 11  nhãn nhỏ nhất 5: ((2,5),9) 4 3  Cập nhật: 8  S = S+{5} = {1, 2, 3, 4, 6, 7, 5} 4 1 2  T = T+{(2,5)} = {(1,6), (6,7), (4,6), (1,2), 1 9 5 (7,3), (2,5)} 12  w(J) = 17+9 = 26 6 7 10 5 2  7)- Vì S = {1, 6, 7 , 4 , 2 , 3 , 5} = X 7 3 6 11  kết thúc giải thuật 4 3 8 77
  78. BÀI TẬP Đề thi 2012, lần 1 Tìm cây khung có trọng lượng nhỏ nhất trong đồ thị được cho bởi ma trận trọng số sau A B C D E F G H K A 1 1 1 B 9 2 8 C 6 2 D 1 5 4 3 E 2 F 9 3 G 9 H 7 K 78
  79. BÀI TẬP Đề thi 2010, lần 2  Khởi tạo  s= 1 S = {1}  T =  w(J) = 0  Các bước lặp  1)- Với S = {1} X thực hiện  Xác định M = {2, 3,4,5,6, 7} Gán nhãn cho các đỉnh trong M  2: ((1,2),7) Cập nhật:  3: ((1,3),8) S = S +{2} = {1,2}  4: ((1,4),9) T = T + {(1,2)}={(1,2)} w(J) = 0 + 7 =7  5: ((1,5),10)  6: ((1,6),11) 79  7: ((1,7),12)
  80. Bài tập Đề thi 2010, lần 2 80  Dùng giải thuật Prim trình bày cách tìm cây khung có trọng lượng nhỏ nhất (cây bao trùm tối tiểu) trên đồ thị vô hướng G có ma trận trọng số được cho như sau : G 1 2 3 4 5 6 7 1 7 8 9 10 11 12 2 1 6 3 2 4 3 5 4 6 5 7
  81. Bài tập Đề thi 2010, lần 2 81  Đỉnh chọn trước là 1  Các cạnh thêm vào cây : (1,7), (1,2), (1,6), (1,4), (4,3), (4,5)  Vẽ cây khung có trọng lượngG nhỏ1 2 nhất. 3 4 5 6 7 1 7 8 9 10 11 12 1 2 3 2 1 6 6 2 3 2 7 8 4 3 9 7 1 1 4 5 4 2 1 11 6 5 5 0 3 7 4 6 5
  82. Bài tập Đề thi 2010, lần 2 82 1 2 3  Khởi tạo 6 2 8  s= 1 S = {1} 7 9  T =  w(J) = 0 7 1 1 4 2 1  Các bước lặp 11 5 0  1)- Với S = {1} X thực hiện 3 4  Xác định M = {2, 3,4,5,6, 7} 6 5 Gán nhãn cho các đỉnh trong M  2: ((1,2),7) Cập nhật:  3: ((1,3),8) S = S +{2} = {1,2}  4: ((1,4),9) T = T + {(1,2)}={(1,2)} w(J) = 0 + 7 =7  5: ((1,5),10)  6: ((1,6),11)  7: ((1,7),12)
  83. Bài tập Đề thi 2010, lần 2 83 1  Các bước lặp 2 3 6 2 8  2)- Với S = {1,2} X thực hiện 7 9  Xác định M = { 3,4,5,6, 7} 7 12 1 4 1 Gán nhãn cho các đỉnh trong M 11 5 0 3  3: ((2,3),1) 4 6 5  4: ((1,4),9)  5: ((1,5),10) Cập nhật:  6: ((1,6),11) S = S +{3} = {1,2,3}  7: ((2,7),6) T = T + {(2,3)}={(1,2),(2,3)} w(J) = 7 + 1 =8
  84. Bài tập Đề thi 2010, lần 2 84 1  Các bước lặp 2 3 6 2 8  3)- Với S = {1,2,3} X thực hiện 7 9  Xác định M = {4,5,6, 7} 7 12 1 4 Gán nhãn cho các đỉnh trong M 11 10 5 3  4: ((3,4),2) 4 6 5  5: ((1,5),10)  6: ((1,6),11) Cập nhật:  7: ((2,7),6) S = S +{4} = {1,2,3,4} T = T + {(3,4)}={(1,2),(2,3),(3,4)} w(J) = 8 + 2 =10
  85. Bài tập Đề thi 2010, lần 2 85 1  Các bước lặp 2 3 6 2 8  4)- Với S = {1,2,3,4} X thực hiện 7 9  Xác định M = {5,6, 7} 7 12 1 4 Gán nhãn cho các đỉnh trong M 11 10 5 3  5: ((4,5),3) 4 6 5  6: ((1,6),11)  7: ((2,7),6) Cập nhật: S = S +{5} = {1,2,3,4,5} T = T + {(4,5)}={(1,2),(2,3),(3,4),(4,5)} w(J) = 10 + 3 = 13
  86. Bài tập Đề thi 2010, lần 2 86 1  Các bước lặp 2 3 6 2 8  5)- Với S = {1,2,3,4,5} X 7 9  Xác định M = {6, 7} 7 12 1 4 Gán nhãn cho các đỉnh trong M 11 10 5 3  6: ((5,6),4) 4 6 5  7: ((2,7),6) Cập nhật: S = S +{6} = {1,2,3,4,5,6} T = T + {(5,6)}={(1,2),(2,3),(3,4),(4,5),(5,6)} w(J) = 13 + 4 = 17
  87. Bài tập Đề thi 2010, lần 2 87 1  Các bước lặp 2 3 6 2 8  5)- Với S = {1,2,3,4,5,6} X 7 9  Xác định M = { 7} 7 12 1 4 Gán nhãn cho các đỉnh trong M 11 10 5 3  7: ((6,7),5) 4 6 5 Cập nhật: S = S +{7} = {1,2,3,4,5,6,7} T = T + {(5,6)}={(1,2),(2,3),(3,4),(4,5),(5,6),(6,7)} w(J) = 17 + 5 = 22 S=X => giải thuật dừng: cây có trọng lượng bằng 22
  88. Bài tập Đề thi 2010, lần 2 88 1 2 3 6 2 7 8 9 7 1 4 12 w(J)=22 10 5 11 3 4 6 5
  89. Bài tập 89  Tìm cây khung có trọng số nhỏ nhất từ đồ thị sau B 5 C 1 1 2 1 G 1 A 1 6 D F 3 7 1 4 9 H E 8
  90. Bài tập 90  Khởi tạo B C  s= A S = {A} 5 1 1 2  T =  w(J) = 0 1 G  Các bước lặp 1 A 1 6 D  1)- Với S = {A} X thực hiện F  Xác định M = {B,F,H} 3 7 1 Gán nhãn cho các đỉnh trong M 4 9 H E  B: ((A,B),1) 8  F: ((A,F),1)  H: ((A,H),3)  Cập nhật:  S = S +{B} = {A,B}  T = T + {(A,B)}={(A,B)}  w(J) = 0 + 1
  91. Bài tập 91  Các bước lặp B 5 C  2)- Với S = {A,B} X thực hiện 1 1 2 1  Xác định M = {G,C,F,H} G 1 Gán nhãn cho các đỉnh trong M A 1 6 D  C: ((B,C),5) F 3 7 1  G: ((B,G),1) 4 9  F: ((A,F),1) H E 8  H: ((A,H),3)  Cập nhật:  S = S +{F} = {A,B,F}  T = T + {(A,F)}={(A,B),(AF)}  w(J) = 1 + 1 = 2
  92. Bài tập 92  Các bước lặp B C  3)- Với S = {A,B,F} X thực hiện 5 1 1 2  Xác định M = {C,G,D,E,H} 1 Gán nhãn cho các đỉnh trong M G 1 1  C: ((B,C),5) A 6 D F  G: ((B,G),1) 3 7 1  D: ((F,D),6) 4 9 H E  E: ((F,E),1) 8  H: ((A,H),3)  Cập nhật:  S = S +{G} = {A,B,F,G}  T = T + {(B,G)}={(A,B),(AF),BG}  w(J) = 2 + 1 = 3
  93. Bài tập 93  Các bước lặp B 5 C  4)- Với S = {A,B,F,G} X thực hiện 1 1 2 1  Xác định M = {C,D,E,H} G 1 Gán nhãn cho các đỉnh trong M A 1 6 D  C: ((G,C),1) F 3 7 1  D: ((F,D),6) 4 9  E: ((F,E),1) H E 8  H: ((A,H),3)  Cập nhật:  S = S +{C} = {A,B,F,G,C}  T = T + {(G,C)}={(A,B),(AF),(BG),(GC)}  w(J) = 3 + 1 = 4
  94. Bài tập 94  Các bước lặp B 5 C  4)- Với S = {A,B,F,G,C} X thực hiện 1 1 2 1 Xác định M = {E,D,H} G 1 Gán nhãn cho các đỉnh trong M A 1 6 D F E: ((F,E),1) 3 7 1 D: ((C,D),2) 4 9 H E H: ((A,H),3) 8 Cập nhật: S = S +{E} = {A,B,F,G,C,E} T = T + {(FE)}={(A,B),(AF),(BG),(GC),(FE)} w(J) = 4 + 1 = 5
  95. Bài tập 95  Các bước lặp B 5 C  5)- Với S = {A,B,F,G,C,E} X thực hiện 1 1 2 1  Xác định M = {D,H} G 1 Gán nhãn cho các đỉnh trong M A 1 6 D F  D: ((C,D),2) 3 7 1 4 9  H: ((A,H),3) H E  Cập nhật: 8  S = S +{D} = {A,B,F,G,C,E,D}  T = T + {(CD)}={(A,B),(AF),(BG),(GC),(FE),(CD)}  w(J) = 5 + 2 = 7
  96. Bài tập 96  Các bước lặp B 5 C  6)- Với S = {A,B,F,G,C,E,D} X thực hiện 1 1 2 1  Xác định M = {H} G 1 Gán nhãn cho các đỉnh trong M A 1 6 D F  H: ((A,H),3) 3 7 1 4 9  Cập nhật: H E  S = S +{H} = {A,B,F,G,C,E,D,H} 8  T = T + {(AH)}={(A,B),(AF),(BG),(GC),(FE),(CD),(AH)}  w(J) = 7 + 3 = 10 => S= X: giải thuật dừng, cây có trọng lượng = 10
  97. Bài tập 97  Tìm cây khung có trọng số nhỏ nhất từ đồ thị sau  T ={(A,B),(AF),(BG),(GC),(FE),(CD),(AH)} B 5 C 1 1 2 1 G 1 A 1 D F 3 1 H E
  98. BÀI TẬP Đề thi năm 2013 (đợt 1) 98 Thuật toán tìm cây khung tối thiểu (Prim / Kruskal) A B C D E F G H K A 2 1 7 B 2 6 3 1 C 6 3 7 4 D 3 4 9 E 4 8 7 6 F 1 8 6 3 G 7 3 6 2 H 1 7 7 3 2 3 K 4 9 6 3
  99. BÀI TẬP Đề thi năm 2013 (đợt 1) 99 Thuật toán tìm cây khung tối thiểu (Prim / Kruskal) F E A G H K B C D