Bài 3 trang 49 Chuyên đề Toán 11 Cánh diều

Trang trước Trang sau

Bài 3 trang 49 Chuyên đề Toán 11: Giả sử chi phí di chuyển giữa các địa điểm được mô tả ở Hình 33 (đơn vị: nghìn đồng). Ta nên chọn theo chu trình nào đi qua tất cả các địa điểm để tổng chi phí di chuyển là thấp nhất? Chi phí thấp nhất đó bằng bao nhiêu?

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

Lời giải:

Dễ thấy đồ thị Hình 33 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 = 20 nghìn đồng;

Từ B, đỉnh chưa đến gần nhất là C, BC = 30 nghìn đồng;

Từ C, đỉnh chưa đến gần nhất là D, CD = 12 nghìn đồng;

Đến đây không còn đỉnh chưa đến, vì vậy quay về A, DA = 35 nghìn đồng.  

Tổng chi phí di chuyển theo chu trình ABCDA là: 20 + 30 + 12 + 35 = 97 (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

ABCDA

97

B

BADCB

97

C

CDBAC

108

D

DCBAD

97

 

Vậy có ba chu trình ABCDA, BADCB, DCBAD thỏa mãn đề bài và chi phí thấp nhất là 97 nghìn đồng.

Lời giải Chuyên đề Toán 11 Bài 2: Một vài ứng dụng của lí thuyết đồ thị hay, chi tiết khác:

Xem thêm lời giải bài tập Chuyên đề học tập Toán 11 Cánh diều hay, chi tiết khác:

Xem thêm các tài liệu học tốt lớp 11 hay khác:

Trang trước Trang sau
Giải bài tập lớp 11 sách mới các môn học