Bài tập lý thuyết đồ thị - Toán cao cấp c2 | Trường Đại Học Duy Tân
Yêu cầu: Nêu ý tưởng thuật toán và viết các kết quả trung gian trong từng bước lặp (lập bảng), kết quả cuối cùng cần đưa ra tập cạnh và độ dài của cây khung nhỏ nhất. Tài liệu giúp bạn tham khảo, ôn tập và đạt kết quả cao. Mời bạn đọc đón xem!
Môn: Toán cao cấp c2 (mth 102) 130 tài liệu
Trường: Đại học Duy Tân 1.8 K tài liệu
Tác giả:
Preview text:
BÀI TẬP
CHƯƠNG 4. LÝ THUYẾT ĐỒ THỊ
Bài 1: Liệt kê kết quả từng bước thực hiện duyệt đồ thị theo 2 dạng: + Duyệt sâu (DFS) + Duyệt rộng (BFS)? a b c e d f g m h k
Bài 2: Hãy tìm cây khung nhỏ nhất bằng thuật toán Prim và thuật toán Kruskal
của đồ thị được cho bởi ma trận trọng số sau. A B C D E F H I
A 14 17 19 23 22 32 18 B 14 33 15 34 19 20 12 C 17 33 13 29 21 20 19 D 19 15 13 22 30 31 11 .
E 23 34 29 22 34 23 21 F 22 19 21 30 34 17 16
H 32 20 20 31 23 17 14
I 18 12 19 11 21 16 14
Yêu cầu: Nêu ý tưởng thuật toán và viết các kết quả trung gian trong từng bước lặp
(lập bảng), kết quả cuối cùng cần đưa ra tập cạnh và độ dài của cây khung nhỏ nhất.
Bài 3: Tìm cây khung của đồ thị sau theo 2 thuật toán duyệt sâu (DFS), duyệt rộng (BFS)? -----------------------