Giải mục 2 trang 47, 48, 49 Chuyên đề học tập Toán 11 - Kết nối tri thức>
Giả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
Đề 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.
- Giải bài 2.15 trang 49 Chuyên đề học tập Toán 11 Kết nối tri thức
- Giải bài 2.16 trang 49 Chuyên đề học tập Toán 11 Kết nối tri thức
- Giải bài 2.17 trang 49 Chuyên đề học tập Toán 11 Kết nối tri thức
- Giải bài 2.18 trang 49 Chuyên đề học tập Toán 11 Kết nối tri thức
- Giải mục 1 trang 46 Chuyên đề học tập Toán 11 - Kết nối tri thức
>> Xem thêm
Luyện Bài Tập Trắc nghiệm Toán 11 - Kết nối tri thức - Xem ngay
Các bài khác cùng chuyên mục
- Giải bài 3.24 trang 81 Chuyên đề học tập Toán 11 Kết nối tri thức
- Giải bài 3.23 trang 81 Chuyên đề học tập Toán 11 Kết nối tri thức
- Giải bài 3.22 trang 81 Chuyên đề học tập Toán 11 Kết nối tri thức
- Giải bài 3.21 trang 80 Chuyên đề học tập Toán 11 Kết nối tri thức
- Giải bài 3.20 trang 80 Chuyên đề học tập Toán 11 Kết nối tri thức
- Giải bài 3.24 trang 81 Chuyên đề học tập Toán 11 Kết nối tri thức
- Giải bài 3.23 trang 81 Chuyên đề học tập Toán 11 Kết nối tri thức
- Giải bài 3.22 trang 81 Chuyên đề học tập Toán 11 Kết nối tri thức
- Giải bài 3.21 trang 80 Chuyên đề học tập Toán 11 Kết nối tri thức
- Giải bài 3.20 trang 80 Chuyên đề học tập Toán 11 Kết nối tri thức