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

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.