Giải bài tập Luyện tập 2 trang 46 Chuyên đề Toán 11 | Chuyên đề học tập Cánh diều
Hướng dẫn giải chi tiết từng bước bài tập Luyện tập 2 trang 46 Chuyên đề Toán 11. Bài 2. Một vài ứng dụng của lí thuyết đồ thị. Chuyên đề học tập Cánh diều
Đề bài:
Sử dụng thuật toán láng giềng gần nhất để giải bài toán trong Hoạt động 2.
Đáp án và cách giải chi tiết:
Dễ thấy đồ thị Hình 24 có chu trình Hamilton.
+) Sử dụng thuật toán láng giềng gần nhất đối với đỉnh xuất phát A, ta có:
Từ A, đỉnh gần nhất là B, AB = 3 km;
Từ B, đỉnh chưa đến gần nhất là C, BC = 5 km;
Từ C, đỉnh chưa đến gần nhất là D, CD = 5 km;
Từ D, đỉnh chưa đến gần nhất là E, DE = 9 km;
Từ E, đỉnh chưa đến gần nhất là F, EF = 6 km;
Đến đây không còn đỉnh chưa đến, vì vậy quay về A, FA = 4 km.
Tổng quãng đường theo chu trình ABCDEFA là: 3 + 5 + 5 + 9 + 6 + 4 = 32 (km).
Tương tự bắt đầu với những đỉnh khác, ta có bảng sau:
Vậy người giao hàng chọn 1 đường đi trong 7 đường đi trên thì quãng đường phải di chuyển là ngắn nhất.
Nguồn: giaitoanhay.com
Tổng số đánh giá:
Xếp hạng: / 5 sao