Tìm chi phí thấp nhất của xe giao hàng (tính theo đơn vị nghìn đồng)?

Đá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.