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
- 250+ Công thức giải nhanh môn Toán 12 (chương trình mới) ( 18.000₫ )
- 20 đề thi tốt nghiệp môn Toán (có đáp án chi tiết) ( 38.500₫ )
- 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Ủ ĐỀ
Câu 1
Lời giải
Tổng số học sinh của mỗi khối 10; 11 đều bằng 540 \( \Rightarrow {N_{K10}} = {N_{K11}} = 540\).

a) Điểm trung bình của khối 11 là:
\(\overline {{x_{K11}}} = \frac{{1,5.1 + 2,5.4 + 3,5.35 + 4,5.86 + 5,5.117 + 6,5.112 + 7,5.102 + 8,5.64 + 9,5.19}}{{540}} = \frac{{1691}}{{270}} \approx 6,26\)
Vậy a) là mệnh đề sai.
b)

Ta có: \(\frac{{{N_{K10}}}}{4} = 135 \Rightarrow \) Xét nhóm 3 có: \(r = 3,\,\,c{f_2} = 63,\,\,{n_3} = 118,\,\,d = 1\).
\({Q_1} = 3 + \frac{{135 - 63}}{{118}}.1 = \frac{{213}}{{59}}\)
Ta có: \(\frac{{3{N_{K10}}}}{4} = 405 \Rightarrow \) Xét nhóm 6 có: \(r = 6,\,\,c{f_5} = 397,\,\,{n_6} = 62,\,\,d = 1\).
\({Q_3} = 6 + \frac{{405 - 379}}{{62}}.1 = \frac{{199}}{{31}}\)
Vậy \(\Delta {Q_{K10}} = {Q_3} - {Q_1} = \frac{{199}}{{31}} - \frac{{213}}{{59}} \approx 2,81\).
Vậy b) là mệnh đề sai.
c) Khối 10:
\(\overline {{x_{K10}}} = \frac{{1,5.11 + 2,5.52 + 3,5.118 + 4,5.121 + 5,5.95 + 6,5.62 + 7,5.47 + 8,5.27 + 9,5.7}}{{540}} = \frac{{1339}}{{270}}\)
\( \Rightarrow {s_{K10}} \approx 1,77\)
Khối 11: \(\overline {{x_{K11}}} = \frac{{1691}}{{270}} \Rightarrow {s_{K11}} \approx 1,59\)
Ta thấy: \({s_{K10}} > {s_{K11}}\). Suy ra, học sinh khối 11 có điểm đồng đều hơn điểm học sinh khối 10.
Vậy c) là mệnh đề sai.
d) \(R = 10 - 1 = 9\).
Vậy d) là mệnh đề đúng.
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
b) Đồ thị \((C)\) như hình vẽ dưới đây.

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.

