Một người đưa thư xuất phát từ bưu điện (vị trí A) và phải đi qua các địa điểm B, C, D để phát thư (mỗi địa điểm chỉ qua một lần) rồi quay lại bưu điện. Sơ đồ các địa điểm cần đi và thời gian (đơn vị: phút) di chuyển qua lại giữa các điểm được mô tả ở hình vẽ bên dưới. Thời gian đi ít nhất của người đưa thư là bao nhiêu phút?

Quảng cáo
Trả lời:
Đáp án:
Yêu cầu bài toán:
Tìm ra chu trình Hamilton có tổng trọng số ngắn nhất: \(A \to \ldots \to \ldots \to \ldots \to A\)
Cách 1: Láng giềng gần (không phải cách chặt chẽ)
· Từ A có 3 sự lựa chọn:
o \( \to C:15\)
o \( \to D:30\)
o \( \to B:42\)
\( \Rightarrow \) Chọn C vì 15 là nhỏ nhất.
· Từ C có 2 sự lựa chọn (không về A nữa):
o \( \to B:34\)
o \( \to D:35\)
\( \Rightarrow \) Chọn B.
· Từ B có 1 sự lựa chọn (không về A, C nữa):
o \( \to D:20\)
· Từ D về A: 30
Tổng chu trình:
15 + 34 + 20 + 30 = 99
Cách 2: Loại bỏ đường đi (không dùng được cho mọi bài)
Nhận xét: Chu trình Hamilton luôn đi qua mỗi đỉnh đúng 1 lần \( \to \) mỗi đỉnh sẽ có 1 đường vào, 1 đường ra.
Mà mỗi đỉnh trong 4 đỉnh lại có tận 3 đường (3 cạnh) nối với nó.
\( \Rightarrow \) Loại bỏ 2 cạnh không chung đỉnh có tổng trọng số lớn nhất:
· Loại AB, CD: \(42 + 35 = 77\) (Lớn nhất \( \to \) Chọn bỏ)
· Loại AC, BD: \(15 + 20 = 35\)
· Loại AD, BC: \(30 + 34 = 64\)
\( \Rightarrow \) Chọn bỏ cạnh AB và CD.
Tổng trọng số:
= (Tất cả các cạnh) - (AB + CD)
\( = 176 - 77 = {\bf{99}}\).
Đáp án: 99.
Hot: 1000+ Đề thi giữa kì 2 file word cấu trúc mới 2026 Toán, Văn, Anh... lớp 1-12 (chỉ từ 60k). Tải ngay
- 20 đề thi tốt nghiệp môn Toán (có đáp án chi tiết) ( 38.500₫ )
- 250+ Công thức giải nhanh môn Toán 12 (chương trình mới) ( 18.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₫ )
- Tổng ôn lớp 12 môn Toán, Lí, Hóa, Văn, Anh, Sinh Sử, Địa, KTPL (Form 2025) ( 36.000₫ )
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Lời giải
Đáp án: 50.
Lợi nhuận mà \(A\) thu được khi bán \(x\) tấn sản phẩm \((0 \le x \le 100)\) cho \(B\) là
\(H(x) = xP(x) - C(x) = x(90 - 0,01{x^2}) - (100 + 15x) = - 0,01{x^3} + 75x - 100\)
\(H(x) = - 0,01{x^3} + 75x - 100\)
\(H\prime (x) = - 0,03{x^2} + 75\)
\(H'\left( x \right) = 0 \Leftrightarrow \left[ \begin{array}{l}x = 50\\x = - 50\end{array} \right.\).
Bảng biến thiên

Từ bảng biến thiên ta có \(A\) bán cho \(B\) \(50\) tấn sản phẩm thì lợi nhuận là lớn nhất.
Câu 2
Lời giải
a) Sai.
Do \(SA = SB = AB = 3\sqrt 2 \) nên \(\Delta SAB\) đều, có trọng tâm \(G\)\( \Rightarrow BG = 3\sqrt 2 \times \frac{{\sqrt 3 }}{2} = \frac{{3\sqrt 6 }}{2}\).
b) Đúng.
c) Sai.
Hình vuông \(ABCD\) có \(AB = 3\sqrt 2 \Rightarrow OC = \frac{{AC}}{2} = \frac{{3\sqrt 2 \times \sqrt 2 }}{2} = 3 \Rightarrow C\left( {0;3;0} \right)\).
d) Đúng.
Ta có: \(A\left( {0; - 3;0} \right)\), \(B\left( {3;0;0} \right)\), \(SO = \sqrt {S{A^2} - O{A^2}} = \sqrt {{{\left( {3\sqrt 2 } \right)}^2} - {3^2}} = 3 \Rightarrow S\left( {0;0;3} \right)\).
Suy ra, tọa độ trọng tâm: \(\left\{ \begin{array}{l}{x_G} = \frac{{0 + 3 + 0}}{3} = 1\\{y_G} = \frac{{ - 3 + 0 + 0}}{3} = - 1\\{z_G} = \frac{{0 + 0 + 3}}{3} = 1\end{array} \right. \Rightarrow G\left( {1; - 1;1} \right)\).
Gọi \(G'\) là điểm đối xứng với \(G\) qua mặt phẳng \(\left( {Oyz} \right)\)\( \Rightarrow G'\left( { - 1; - 1;1} \right)\).
Xét \(KG + KB = KG' + KB \ge G'B\), dấu bằng xảy ra khi ba điểm \(B\), \(K\), \(G'\) thẳng hàng.
Khi đó: \(\overrightarrow {G'K} = \left( {1;m + 1;n - 1} \right)\) cùng phương với \(\overrightarrow {G'B} = \left( {4;1; - 1} \right)\)
\( \Rightarrow \frac{1}{4} = \frac{{m + 1}}{1} = \frac{{n - 1}}{{ - 1}} \Rightarrow \left\{ \begin{array}{l}m = - \frac{3}{4}\\n = \frac{3}{4}\end{array} \right. \Rightarrow {m^2} + {n^2} = \frac{9}{8}\).
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 4
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.

