Câu hỏi:
24/05/2025 20
Một công ty vận tải cần giao hàng đến tất cả các thành phố \(A\), \(B\), \(C\), \(D\), \(E\) (hình vẽ). Chi phí di chuyển giữa các thành phố được mô tả trên hình (tính theo đơn vị nghìn đồng). Xe giao hàng của công ty xuất phát từ thành phố \(A\) đi qua tất cả các thành phố còn lại đúng một lần sau đó trở lại thành phố \(A\). Tìm chi phí thấp nhất của xe giao hàng (tính theo đơn vị nghìn đồng)?
Một công ty vận tải cần giao hàng đến tất cả các thành phố \(A\), \(B\), \(C\), \(D\), \(E\) (hình vẽ). Chi phí di chuyển giữa các thành phố được mô tả trên hình (tính theo đơn vị nghìn đồng). Xe giao hàng của công ty xuất phát từ thành phố \(A\) đi qua tất cả các thành phố còn lại đúng một lần sau đó trở lại thành phố \(A\). Tìm chi phí thấp nhất của xe giao hàng (tính theo đơn vị nghìn đồng)?
Quảng cáo
Trả lời:
Giải bởi Vietjack
Đáp án: 5300.
Cách 1: Liệt kê các đường đi có thể liên thông
Các hành trình có thể và chi phí tương ứng:
1. \(A \to B \to E \to C \to D \to A\): \(900 + 800 + 1200 + 1300 + 1100 = 5300\)
2. \(A \to B \to E \to D \to C \to A\): \(900 + 800 + 1400 + 1300 + 1200 = 5600\)
3. \(A \to B \to C \to E \to D \to A\): \(900 + 1400 + 1200 + 1400 + 1100 = 6000\)
4. \(A \to B \to C \to D \to E \to A\): \(900 + 1400 + 1300 + 1400 + 1000 = 6000\)
5. \(A \to E \to B \to C \to D \to A\): \(1000 + 800 + 1400 + 1300 + 1100 = 5600\)
6. \(A \to E \to D \to C \to B \to A\): \(1000 + 1400 + 1300 + 1400 + 900 = 6000\)
7. \(A \to D \to C \to B \to E \to A\): \(1100 + 1300 + 1400 + 800 + 1000 = 5600\)
8. \(A \to D \to C \to E \to B \to A\): \(1100 + 1300 + 1200 + 800 + 900 = 5300\)
9. \(A \to D \to E \to B \to C \to A\): \(1100 + 1400 + 800 + 1400 + 1200 = 5900\)
10. \(A \to D \to E \to C \to B \to A\): \(1100 + 1400 + 1200 + 1400 + 900 = 6000\)
Kết luận: Chi phí thấp nhất mà xe tải của công ty vận tải phải trả là \(5300\) nghìn đồng, ứng với các hành trình:
1. \(A \to B \to E \to C \to D \to A\)
8. \(A \to D \to C \to E \to B \to A\)
@ Cách 2: Lý thuyết đồ thị
⮚ Hình bên là một đơn đồ thị liên thông có \(5\) đỉnh.
⮚ Do bậc của các đỉnh đều lớn hơn hoặc bằng \(3\) nên đồ thị có chu trình Hamilton.
Chúng ta cần tìm một chu trình Hamilton có tổng trọng số nhỏ nhất trong đồ thị đã cho, bắt đầu và kết thúc tại đỉnh \(A\).
Dùng phương pháp gắn nhãn ta thấy chu trình \(A \to B \to E \to C \to D \to A\) có chi phí thấp nhất là \(5300\) nghìn đồng.
Chu trình ngược lại \(A \to D \to C \to E \to B \to A\) cũng có chi phí tương đương:
\[1100 + 1300 + 1200 + 800 + 900 = 5300\].
Vậy, chi phí thấp nhất mà xe hàng phải trả là \(5300\) nghìn đồng.
Hot: 500+ Đề thi thử tốt nghiệp THPT các môn, ĐGNL các trường ĐH... file word có đáp án (2025). Tải ngay
Sách thầy cô Vietjack biên soạn:
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)
Đã bán 986
₫ 70.000
₫ 36.000
Tổng ôn lớp 12 môn Toán, Lí, Hóa, Văn, Anh, Sinh Sử, Địa, KTPL (Form 2025)
Đã bán 1,1k
₫ 70.000
₫ 36.000
Bình luận
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 3:
PHẦN III. Câu trắc nghiệm trả lời ngắn. Thí sinh trả lời từ câu 1 đến câu 6.
Nhà máy \(A\) chuyên sản xuất một loại sản phẩm cho nhà máy \(B\). Hai nhà máy thoả thuận rằng, hàng tháng nhà máy \(A\) cung cấp cho nhà máy \(B\) số lượng sản phẩm theo đơn đặt hàng của nhà máy \(B\) (tối đa \(100\) tấn sản phẩm). Nếu số lượng đặt hàng là \(x\) tấn sản phẩm thì giá bán cho mỗi tấn sản phẩm là \(p\left( x \right) = 90 - 0,01{x^2}\) (đơn vị: triệu đồng). Chi phí để nhà máy \(A\) sản xuất \(x\) tấn sản phẩm trong một tháng là \(C\left( x \right) = \frac{1}{2}\left( {200 + 27x} \right)\) (đơn vị: triệu đồng), thuế giá trị gia tăng mà nhà máy \(A\) phải đóng cho nhà nước là \(10\% \) tổng doanh thu mỗi tháng. Hỏi nhà máy \(A\) bán cho nhà máy \(B\) bao nhiêu tấn sản phẩm để mỗi tháng thu được lợi nhuận (sau khi đã trừ thuế giá trị gia tăng) cao nhất?
PHẦN III. Câu trắc nghiệm trả lời ngắn. Thí sinh trả lời từ câu 1 đến câu 6.
Nhà máy \(A\) chuyên sản xuất một loại sản phẩm cho nhà máy \(B\). Hai nhà máy thoả thuận rằng, hàng tháng nhà máy \(A\) cung cấp cho nhà máy \(B\) số lượng sản phẩm theo đơn đặt hàng của nhà máy \(B\) (tối đa \(100\) tấn sản phẩm). Nếu số lượng đặt hàng là \(x\) tấn sản phẩm thì giá bán cho mỗi tấn sản phẩm là \(p\left( x \right) = 90 - 0,01{x^2}\) (đơn vị: triệu đồng). Chi phí để nhà máy \(A\) sản xuất \(x\) tấn sản phẩm trong một tháng là \(C\left( x \right) = \frac{1}{2}\left( {200 + 27x} \right)\) (đơn vị: triệu đồng), thuế giá trị gia tăng mà nhà máy \(A\) phải đóng cho nhà nước là \(10\% \) tổng doanh thu mỗi tháng. Hỏi nhà máy \(A\) bán cho nhà máy \(B\) bao nhiêu tấn sản phẩm để mỗi tháng thu được lợi nhuận (sau khi đã trừ thuế giá trị gia tăng) cao nhất?
Xem đáp án »
24/05/2025
47
Câu 4:
a) Hàm số \(h\left( t \right)\) có công thức là \(h\left( t \right) = - 0,005{t^4} + 0,1{t^3}\).
a) Hàm số \(h\left( t \right)\) có công thức là \(h\left( t \right) = - 0,005{t^4} + 0,1{t^3}\).
Xem đáp án »
24/05/2025
31
Câu 5:
Bảng sau thống kê thời gian tập thể dục mỗi ngày trong tháng 3/2025 của hai bạn Hưng và Bình.
Thời gian (phút)
\[\left[ {10;15} \right)\]
\[\left[ {15;20} \right)\]
\[\left[ {20;25} \right)\]
\[\left[ {25;30} \right)\]
\[\left[ {30;35} \right)\]
Số ngày tập của Hưng
\[2\]
\[14\]
\[8\]
\[3\]
\[3\]
Số ngày tập của Bình
\[12\]
\[8\]
\[7\]
\[3\]
\[0\]
Khoảng biến thiên của mẫu số liệu ghép nhóm về thời gian tập của Hưng và Bình lần lượt là
Bảng sau thống kê thời gian tập thể dục mỗi ngày trong tháng 3/2025 của hai bạn Hưng và Bình.
|
Thời gian (phút) |
\[\left[ {10;15} \right)\] |
\[\left[ {15;20} \right)\] |
\[\left[ {20;25} \right)\] |
\[\left[ {25;30} \right)\] |
\[\left[ {30;35} \right)\] |
|
Số ngày tập của Hưng |
\[2\] |
\[14\] |
\[8\] |
\[3\] |
\[3\] |
|
Số ngày tập của Bình |
\[12\] |
\[8\] |
\[7\] |
\[3\] |
\[0\] |
Xem đáp án »
24/05/2025
25
Câu 6:
PHẦN I. Câu trắc nghiệm nhiều phương án lựa chọn. Thí sinh trả lời từ câu 1 đến câu 12. Mỗi câu thí sinh chỉ chọn một phương án.
Cho hàm số \[y = f\left( x \right)\] có đồ thị như hình dưới đây.
Biểu thức \[f\left( x \right)\] là biểu thức nào sau đây?
PHẦN I. Câu trắc nghiệm nhiều phương án lựa chọn. Thí sinh trả lời từ câu 1 đến câu 12. Mỗi câu thí sinh chỉ chọn một phương án.
Cho hàm số \[y = f\left( x \right)\] có đồ thị như hình dưới đây.
Xem đáp án »
24/05/2025
20
🔥 Đề thi HOT:
-
30 Đề thi thử thpt quốc gia môn Toán có lời giải chi tiết mới nhất (Đề số 1)
-
(2025 mới) Đề thi ôn tập THPT môn Toán có đáp án (Đề số 1)
-
CÂU TRẮC NGHIỆM ĐÚNG SAI
-
Đề minh họa tốt nghiệp THPT môn Toán có đáp án năm 2025 (Đề 1)
-
Đề minh họa tốt nghiệp THPT môn Toán có đáp án năm 2025 (Đề 2)
-
(2025 mới) Đề thi ôn tập THPT môn Toán có đáp án (Đề số 2)
-
Đề minh họa tốt nghiệp THPT môn Toán có đáp án năm 2025 (Đề 19)
-
(2025 mới) Đề thi ôn tập THPT môn Toán có đáp án (Đề số 5)
Hãy Đăng nhập hoặc Tạo tài khoản để gửi bình luận
-
-
Bình luận