Với giải Luyện tập 2 trang 46 Chuyên đề Toán 11 Cánh diều chi tiết trong Bài 2: Một vài ứng dụng của lí thuyết đồ thị giúp học sinh dễ dàng xem và so sánh lời giải từ đó biết cách làm bài tập Chuyên đề Toán 11. Mời các bạn đón xem:
Giải Chuyên đề Toán 11 Bài 2: Một vài ứng dụng của lí thuyết đồ thị
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:
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.
Xem thêm lời giải bài tập Chuyên đề học tập Toán lớp 11 Cánh diều hay, chi tiết khác:
Luyện tập 1 trang 44 Chuyên đề Toán 11: Hãy cho ví dụ về đồ thị có trọng số....
Xem thêm bài giải Chuyên đề học tập Toán lớp 11 Cánh diều hay, chi tiết khác:
Bài 1: Một vài yếu tố của lí thuyết đồ thị. Đường đi Euler và đường đi Hamilton
Bài 2: Một vài ứng dụng của lí thuyết đồ thị
Bài 1: Một số nội dung cơ bản về vẽ kĩ thuật
Bài 2: Đọc và vẽ bản vẽ kĩ thuật đơn giản
Xem thêm các bài Chuyên đề học tập Toán lớp 11 Cánh diều hay, chi tiết khác:
Chuyên đề 2: Làm quen với một vài yếu tố của lí thuyết đồ thị
CÔNG TY TNHH ĐẦU TƯ VÀ DỊCH VỤ GIÁO DỤC VIETJACK
- Người đại diện: Nguyễn Thanh Tuyền
- Số giấy chứng nhận đăng ký kinh doanh: 0108307822, ngày cấp: 04/06/2018, nơi cấp: Sở Kế hoạch và Đầu tư thành phố Hà Nội.
© 2021 Vietjack. All Rights Reserved.
