Bài 4 trang 49 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, hãy giải bài toán người giao hàng đối với đồ thị ở Hình 34, số ghi trên mỗi cạnh của đồ thị mô tả độ dài quãng đường giữa các địa điểm (đơn vị: kilômét).

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

3. Lời giải chi tiết

Dễ thấy đồ thị Hình 34 có chu trình Hamilton.

Ta thấy chu trình xuất phát từ đỉnh A là AEDBCA thỏa mãn đề bài với tổng quãng đường nhỏ nhất là AE + ED + DB + BC + CA = 5 + 5 + 3 + 5 + 3 = 21 (km).

Các chu trình xuất phát từ đỉnh B, C, D, E  có 1 đỉnh được đi qua hai lần nên không thỏa mãn quy tắc của thuật toán láng giềng gần nhất nên loại.