Luyện tập 2 trang 46 Chuyên đề Toán 11 Cánh diều

1. Nội dung câu hỏ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.

2. Phương pháp giải 

3. Lời 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.