Giải bài tập Bài 4 trang 49 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 Bài 4 trang 49 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, 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).
Đáp án và cách 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.
Nguồn: giaitoanhay.com
Tổng số đánh giá:
Xếp hạng: / 5 sao