Giải mục 2 trang 47, 48, 49 Chuyên đề học tập Toán 11 - Kết nối tri thứcGiải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.32. Tổng hợp đề thi giữa kì 1 lớp 11 tất cả các môn - Kết nối tri thức Toán - Văn - Anh - Lí - Hóa - Sinh Quảng cáo
Đề bài Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.32.
Phương pháp giải - Xem chi tiết Giải bài tán bằng thuật toán tìm đường đi ngắn nhất: Ta xuất phát từ đỉnh A và di chuyển theo các cạnh của đồ thị. Với mỗi đỉnh V, ta gắn một số \(I(V)\) là khoảng cách ngắn nhất để đi từ A đến V, gọi là nhãn vĩnh viễn của đỉnh V. Như vậy, để tìm độ dài của đường đi ngắn nhất nối A với F, ta cần tìm \(I(F)\). Lời giải chi tiết Đồ thị Hình 2.32 chỉ có hai đỉnh bậc lẻ là A và D nên ta có thể tìm được một đường đi Euler từ A đến D (đường đi này đi qua mỗi cạnh đúng một lần). Một đường đi Euler từ A đến D là AFEABEDBCD và tổng độ dài của nó là 10 + 9 + 7 + 2 + 8 + 16 + 15 + 3 + 4 = 74. Để quay trở lại điểm xuất phát và có đường đi ngắn nhất, ta cần tìm một đường đi ngắn nhất từ D đến A theo thuật toán gắn nhãn vĩnh viễn. Đường đi ngắn nhất từ D đến A là DCBA và có độ dài là 4 + 3 + 2 = 9. Vậy một chu trình cần tìm là AFEABEDBCDCBA và có độ dài là 74 + 9 = 83.  Chia sẻ Bình luận
Quảng cáo
Tham Gia Group Dành Cho 2K8 Chia Sẻ, Trao Đổi Tài Liệu Miễn Phí
|
