Câu hỏi:

117 lượt xem
Tự luận

Bài 4 trang 49 Chuyên đề Toán 11Sử 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).

Bài 4 trang 49 Chuyên đề học tập Toán 11 Cánh diều

 

Xem đáp án

Lời giải

Hướng dẫn giải:

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. 

CÂU HỎI HOT CÙNG CHỦ ĐỀ