Luyện tập 2 trang 46 Chuyên đề Toán 11 Cánh diều

Trang trước Trang sau

Luyện tập 2 trang 46 Chuyên đề Toán 11: Sử dụng thuật toán láng giềng gần nhất để giải bài toán trong Hoạt động 2.

Lời giải:

Luyện tập 2 trang 46 Chuyên đề học tập Toán 11 Cánh diều

Dễ thấy đồ thị Hình 24 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 = 3 km;

Từ B, đỉnh chưa đến gần nhất là C, BC = 5 km;

Từ C, đỉnh chưa đến gần nhất là D, CD = 5 km;

Từ D, đỉnh chưa đến gần nhất là E, DE = 9 km;

Từ E, đỉnh chưa đến gần nhất là F, EF = 6 km;

Đến đây không còn đỉnh chưa đến, vì vậy quay về A, FA = 4 km.

Tổng quãng đường theo chu trình ABCDEFA là: 3 + 5 + 5 + 9 + 6 + 4 = 32 (km).

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ều dài (km)

A

ABCDEFA

32

B

BAFEDCB

32

C

CBAFEDC

32

C

CDEFABC

32

D

DCBAFED

32

E

EFABCDE

32

F

FABCDEF

32

 

Vậy người giao hàng chọn 1 đường đi trong 7 đường đi trên thì quãng đường phải di chuyển là ngắn nhất.

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:

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