Chu trình euler vs Chu trình Hamilton - Bài toán tối ưu

Chu trình euler vs Chu trình Hamilton - Bài toán tối ưu

1. Chu trình Euler là gì?

Chu trình Euler (Eulerian Cycle) là một chu trình trong đồ thị sao cho:

• Đi qua mỗi cạnh đúng một lần duy nhất.

• Xuất phát từ một đỉnh và quay trở về chính đỉnh đó.

Điều kiện tồn tại chu trình Euler:

• Đồ thị liên thông (có đường đi giữa mọi cặp đỉnh).

• Mỗi đỉnh có bậc chẵn (số cạnh nối với đỉnh đó là số chẵn).

Ví dụ: Bài toán "vẽ một đường đi qua tất cả các cầu ở Königsberg" nổi tiếng chính là bài toán chu trình Euler đầu tiên.

---

2. Các loại chu trình khác trong bài toán tối ưu

Ngoài chu trình Euler, trong các bài toán tối ưu hóa (như logistics, giao vận, kỹ thuật…) còn nhiều loại chu trình khác:

---

3. So sánh ngắn gọn

---

4. Một vài bài toán tiêu biểu liên quan đến chu trình trong tối ưu:

• Bài toán Người bán hàng (TSP): Tìm chu trình Hamilton có tổng chi phí nhỏ nhất.

• Bài toán đi qua cầu (Eulerian Path): Đi qua tất cả các cây cầu đúng một lần.

• Bài toán Chinese Postman: Tìm đường đi ngắn nhất đi qua tất cả các cạnh ít nhất một lần (sử dụng khái niệm chu trình Euler mở rộng).

---

5. Tóm lược ngắn gọn

Chu trình Euler: Đi qua mỗi cạnh đúng 1 lần.
Chu trình Hamilton: Đi qua mỗi đỉnh đúng 1 lần.
Chu trình tối ưu: Là chu trình Hamilton hoặc Euler nhưng có thêm tiêu chí tối ưu chi phí/quãng đường.

1. Ví dụ về Chu trình Euler

Bài toán:
Cho đồ thị có 4 đỉnh A, B, C, D, các cạnh:

• A–B, B–C, C–D, D–A, A–C, B–D.

Đồ thị vẽ ra là hình vuông với hai đường chéo.

Quan sát:

• Mỗi đỉnh đều có bậc 3 (lẻ) → Không có chu trình Euler.

• Nếu mình bỏ bớt 2 đường chéo (A–C, B–D), mỗi đỉnh có bậc 2 (chẵn) → Có chu trình Euler.

Một chu trình Euler có thể là: A → B → C → D → A.

---

2. Ví dụ về Chu trình Hamilton

Bài toán:
Cùng đồ thị trên (hình vuông có hai đường chéo).

• Bạn cần đi qua tất cả các đỉnh A, B, C, D đúng một lần rồi quay về.

Một chu trình Hamilton có thể là: A → B → C → D → A.

(Lưu ý: ở đây ta chỉ cần đi qua đỉnh, không cần đi qua tất cả cạnh.)

---

3. Ví dụ về Chu trình tối ưu (TSP)

Bài toán:
Một người cần đi thăm 4 thành phố A, B, C, D với chi phí di chuyển giữa các thành phố như sau:

Yêu cầu: Tìm hành trình đi qua mỗi thành phố đúng một lần rồi quay về điểm xuất phát sao cho chi phí thấp nhất.

Giải nhanh:

• Một hành trình tối ưu có thể là: A → B → D → C → A.

• Tổng chi phí = 10 (A–B) + 25 (B–D) + 30 (D–C) + 15 (C–A) = 80.

---

4. Tổng kết ngắn