Công ty X có một kho hàng trung tâm tại điểm A và cần giao hàng đến 3 điểm giao hàng khác nhau B, C, D trong thành phố, sau khi giao hàng xong thì xe quay về điểm A. Biết rằng khoảng cách giữa các điểm giao hàng cho bởi bảng sau (đơn vị tính km).
|
Điểm đến Điểm đi |
A |
B |
C |
D |
|
A |
0 |
9 |
11 |
14 |
|
B |
9 |
0 |
7 |
8 |
|
C |
11 |
7 |
0 |
5 |
|
D |
14 |
8 |
5 |
0 |
Thời gian giao hàng tại mỗi điểm giao hàng 30 phút/điểm. Tốc độ trung bình của xe vận chuyển hàng là 40km/h. Tính tổng thời gian ít nhất để hoàn thành việc giao hàng nói trên (đơn vị đo: phút, làm tròn đến hàng đơn vị).
Quảng cáo
Trả lời:
Từ giả thiết của đề bài, ta có đồ thị sau:

Ta thấy đây là một đơn đồ thị có 4 đỉnh, mỗi đỉnh đều có bậc là 3 không nhỏ hơn \(\frac{4}{2} = 2\) nên theo định lí Dirac thì đồ thị này có một chu trình Hamilton.
Ta xét tất cả các trường hợp sau:
ABCDA: \(9 + 7 + 5 + 14 = 35\).
ABDCA: \(9 + 8 + 5 + 11 = 33\).
ACBDA: \(11 + 7 + 8 + 14 = 40\).
ACDBA: \(11 + 5 + 8 + 9 = 33\).
ADCBA: \(14 + 5 + 7 + 9 = 35\).
ADBCA: \(14 + 8 + 7 + 11 = 40\).
Vậy con đường ngắn nhất đi từ A qua các kho B, C, D và trở về A ngắn nhất là ABDCA hoặc ACDBA, với quãng đường dài \(33\,\,{\rm{km}}\).
Vậy thời gian tối thiểu là: \(\frac{{33}}{{40}} \cdot 60 + 3 \cdot 30 = 139,5\) (phút).
Kết quả làm tròn đến hàng đơn vị là \(140\).
Đáp án: 140.
Hot: 1000+ Đề thi giữa kì 1 file word cấu trúc mới 2025 Toán, Văn, Anh... lớp 1-12 (chỉ từ 60k). Tải ngay
- 20 Bộ đề, Tổng ôn, sổ tay môn Toán (có đáp án chi tiết) ( 55.000₫ )
- 250+ Công thức giải nhanh môn Toán 12 (chương trình mới) ( 18.000₫ )
- Sổ tay lớp 12 các môn Toán, Lí, Hóa, Văn, Sử, Địa, KTPL (chương trình mới) ( 36.000₫ )
- Bộ đề thi tốt nghiệp 2025 các môn Toán, Lí, Hóa, Văn, Anh, Sinh, Sử, Địa, KTPL (có đáp án chi tiết) ( 36.000₫ )
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Lời giải
Câu 2
Lời giải
Câu 3
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Câu 6
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

