Câu hỏi:
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)?
Trả lời:
Đáp án đúng:
Đây là bài toán tìm chu trình Hamilton có trọng số nhỏ nhất.
Ta có thể liệt kê các hành trình có thể đi và tính tổng chi phí của từng hành trình:
Ta có thể liệt kê các hành trình có thể đi và tính tổng chi phí của từng hành trình:
- $A-B-C-D-E-A$: $4+3+4+5+9 = 25$
- $A-B-C-E-D-A$: $4+3+3+5+8 = 23$
- $A-B-D-C-E-A$: $4+2+4+3+9 = 22$
- $A-B-D-E-C-A$: $4+2+5+3+6 = 20$
- $A-B-E-C-D-A$: $4+7+3+4+8 = 26$
- $A-B-E-D-C-A$: $4+7+5+4+6 = 26$
Câu hỏi này thuộc đề thi trắc nghiệm dưới đây, bấm vào Bắt đầu thi để làm toàn bài
Câu hỏi liên quan

Bộ 50 Đề Thi Thử Tốt Nghiệp THPT Giáo Dục Kinh Tế Và Pháp Luật Năm 2026 – Theo Cấu Trúc Đề Minh Họa Bộ GD&ĐT

Bộ 50 Đề Thi Thử Tốt Nghiệp THPT Lịch Sử Học Năm 2026 – Theo Cấu Trúc Đề Minh Họa Bộ GD&ĐT

Bộ 50 Đề Thi Thử Tốt Nghiệp THPT Công Nghệ Năm 2026 – Theo Cấu Trúc Đề Minh Họa Bộ GD&ĐT

Bộ 50 Đề Thi Thử Tốt Nghiệp THPT Môn Hóa Học Năm 2026 – Theo Cấu Trúc Đề Minh Họa Bộ GD&ĐT

Bộ 50 Đề Thi Thử Tốt Nghiệp THPT Môn Sinh Học Năm 2026 – Theo Cấu Trúc Đề Minh Họa Bộ GD&ĐT
