Câu hỏi:
130 lượt xemLuyện tập 2 trang 46 Chuyên đề Toán 11: 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.
Lời giải
Hướng dẫn giải:
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:
Đỉnh bắt đầu |
Chu trình |
Tổng chiều dài (km) |
A |
ABCDEFA |
32 |
B |
BAFEDCB |
32 |
C |
CBAFEDC |
32 |
C |
CDEFABC |
32 |
D |
DCBAFED |
32 |
E |
EFABCDE |
32 |
F |
FABCDEF |
32 |
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.
Luyện tập 1 trang 44 Chuyên đề Toán 11: Hãy cho ví dụ về đồ thị có trọng số.