Bài toán đếm đường đi Hamilton từ E đến F – Đề V-ACT 2026 đợt 1

Bài toán đếm đường đi Hamilton từ E đến F trong đồ thị. Lời giải nhanh, dễ hiểu, phù hợp học sinh lớp 12 ôn thi ĐGNL ĐHQG-HCM kì thi V-ACT.

Bài toán đếm đường đi Hamilton trong đồ thị - Đề V-ACT 2026

Đề bài

[Đề thi ĐGNL ĐHQG-HCM năm 2026 đợt 1, thi ngày 05/4/2026]

Một khu du lịch gồm $6$ địa điểm \(A, B, C, D, E, F\) được nối với nhau. Bạn Anh Thư muốn đi từ \(E\) lần lượt qua các điểm khác và kết thúc tại \(F\). Số cách đi là:

A. \(3\).
B. \(2\).
C. \(1\).
D. \(4\).

Lời giải

Ta hiểu rằng mỗi địa điểm chỉ được đi qua đúng một lần (bài toán đếm đường đi Hamilton từ \(E\) đến \(F\)).

Từ \(E\), có $2$ lựa chọn để đến địa điểm tiếp theo: \(A, B\).

Xét các khả năng đi hết các điểm mà không lặp:

• \(E \to A \to B \to C \to D \to F\)
• \(E \to B \to A \to D \to C \to F\)

Các cách còn lại không thể đi hết các điểm mà không lặp đỉnh.

Vậy có tất cả \(2\) cách đi.

Đáp án: B.

Ghi chú

- Đây là một bài toán thuộc lĩnh vực đồ thị trong Toán rời rạc, cụ thể là đếm số đường đi Hamilton. Đường đi Hamilton là đường đi qua mỗi đỉnh đúng một lần.

- Trong đề bài, cụm “lần lượt đi qua các điểm khác” được hiểu ngầm là mỗi địa điểm chỉ đi qua một lần. Nếu cho phép lặp đỉnh thì số cách đi sẽ rất lớn (thậm chí vô hạn nếu không chặn bước).

- Dạng bài này thường xuất hiện trong đề thi đánh giá năng lực dưới dạng bài toán thực tế (du lịch, lộ trình, mạng lưới giao thông,...).