29/01/2024
29/01/2024
29/01/2024
6)Dễ thấy đồ thị 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 = 14 nghìn đồng;
Từ B, đỉnh chưa đến gần nhất là D, BD = 30 nghìn đồng;
Từ D, đỉnh chưa đến gần nhất là C, CD = 13 nghìn đồng;
Đến đây không còn đỉnh chưa đến, vì vậy quay về A, CA = 34 nghìn đồng.
Tổng chi phí di chuyển theo chu trình ABDCA là: 14+30+13+34=91 (nghìn đồng).
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 phí ( nghìn đồng)
A ABDCA 91
B BACDB 91
C CDABC 102
D DCABD 91
Vậy có ba chu trình ABDCA , BACDB, DCABD thỏa mãn đề bài và chi phí thấp nhất là 91 nghìn đồng.
Nếu bạn muốn hỏi bài tập
Các câu hỏi của bạn luôn được giải đáp dưới 10 phút
CÂU HỎI LIÊN QUAN
5 giờ trước
5 giờ trước
5 giờ trước
Top thành viên trả lời