Bài toán Chu trình Euler và đường đi Euler?
Bài toán bạn đang làm chính là một bài toán Chu trình Euler – hay cụ thể hơn, là biến thể người đưa thư (Chinese Postman Problem) – trong đồ thị.
🔍 Tóm tắt bài toán Chu trình Euler:
💡 Chu trình Euler là gì?
-
Là một đường đi trong đồ thị vô hướng hoặc có hướng, đi qua mỗi cạnh đúng 1 lần, và bắt đầu – kết thúc tại cùng 1 đỉnh.
✅ Điều kiện tồn tại chu trình Euler (trong đồ thị vô hướng):
-
Tất cả các đỉnh đều có bậc chẵn.
🚀 Đang chuẩn bị thi Đánh giá năng lực (HSA/TSA/SPT/Bộ Công an) hoặc Tốt nghiệp THPT?Đăng ký ngay Khoá Cấp Tốc Đánh Giá Năng Lực & Luyện Đề 9+ Thầy Thế Anh →
Nếu:
-
Có 0 đỉnh bậc lẻ → Tồn tại chu trình Euler (đi rồi quay về điểm xuất phát)
-
Có 2 đỉnh bậc lẻ → Tồn tại đường đi Euler (bắt đầu ở một đỉnh lẻ, kết thúc ở đỉnh lẻ còn lại)
-
Có hơn 2 đỉnh bậc lẻ → Không tồn tại chu trình hoặc đường đi Euler
📌 Bài toán của bạn:
-
Người đưa thư phải đi qua mỗi cạnh ít nhất một lần, bắt đầu và kết thúc tại cùng 1 điểm → chính là Chu trình Euler
-
Nhưng đồ thị có 2 đỉnh bậc lẻ (A và D) → Không tồn tại chu trình Euler ngay
-
→ Phải thêm cạnh nối A–D bằng đường ngắn nhất để tạo chu trình
🔧 Biến thể mở rộng: Bài toán người đưa thư Trung Hoa
Là bài toán tối ưu hóa tổng quãng đường cần đi để đi qua tất cả các cạnh ít nhất một lần và quay về chỗ cũ, kể cả khi đồ thị không có chu trình Euler sẵn.
Cách giải:
-
Tính tổng độ dài các cạnh ban đầu
-
Xác định các đỉnh bậc lẻ
-
Ghép các đỉnh bậc lẻ thành từng cặp sao cho tổng đường ngắn nhất giữa các cặp là nhỏ nhất
-
Cộng phần đường đi thêm đó vào tổng ban đầu → ra đáp án
Trong lý thuyết đồ thị, một đường đi trong đồ thị G = (X, E) được gọi là đường đi Euler nếu nó đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần.
Đường đi Euler có đỉnh cuối cùng trùng với đỉnh xuất phát gọi là chu trình Euler.
Khái niệm chu trình Euler xuất phát từ bài toán bảy cây cầu do Euler giải quyết vào khoảng năm 1737. Đường đi Euler có thể tìm thấy trong các bài toán vui vẽ một nét (vẽ một hình nào đó mà không nhấc bút khỏi mặt giấy, không tô lại cạnh nào hai lần).
Carl Hierholzer là người đầu tiên mô tả hoàn chỉnh đồ thị Euler vào năm 1873, bằng cách chứng minh rằng đồ thi Euler là đồ thị liên thông không có đỉnh bậc lẻ.
🔍 1. Chu trình Euler là gì?
-
Là một đường đi đi qua mọi cạnh đúng 1 lần
-
Bắt đầu và kết thúc tại cùng 1 đỉnh
✅ Ví dụ:
🔍 2. Đường đi Euler là gì?
-
Cũng là một đường đi qua mọi cạnh đúng 1 lần
-
Bắt đầu và kết thúc tại 2 đỉnh khác nhau
✅ Ví dụ:
🧠 So sánh nhanh:
| Tiêu chí | Chu trình Euler | Đường đi Euler |
|---|---|---|
| Đi qua tất cả cạnh | ✅ | ✅ |
| Mỗi cạnh đi đúng 1 lần | ✅ | ✅ |
| Bắt đầu và kết thúc | Cùng 1 đỉnh | Khác 2 đỉnh |
| Điều kiện tồn tại | Tất cả đỉnh bậc chẵn | 2 đỉnh bậc lẻ, còn lại chẵn |
| Kết thúc | Về chỗ cũ | Dừng ở đỉnh khác |
🧩 Ứng dụng:
-
Chu trình Euler: Các bài toán vòng tròn, đưa thư, đi tuần, vẽ một nét về chỗ cũ
-
Đường đi Euler: Đi hết mà không cần quay về
🎁 Tải Tài Liệu Ôn Thi & Mở Khóa Trọn Bộ Đề Tủ Toán Lớp 5 – Lớp 6 & Ôn Vào 6 CLC (2026–2027)
Biên soạn & kiểm duyệt bởi ThS. Nguyễn Thế Anh (Á khoa ĐH Ngoại thương & ĐH Y Hà Nội • 2 Điểm 10 Toán)
📥 Nhận Bản PDF Đề In Sắc Nét + Phác Đồ Rà Lỗ Hổng 8 Tuần
Điền SĐT Zalo để hệ thống gửi ngay file PDF chuẩn in + tư vấn lộ trình học sát lực học hiện tại của con:
9986683218 – Nguyễn Thế Anh📝 Nội dung CK:
TTA PDF HK1T6 + SĐT Zalo
Phụ huynh & học sinh đang tìm lớp Toán nhóm nhỏ kèm sát theo đúng lực học, mục tiêu và khu vực có thể xem chi tiết lộ trình tại:
- 🏫 Lớp học thêm Toán uy tín tại Hà Nội & Zoom trực tuyến (Lớp 6 – Lớp 12)
- 📍 Lớp học thêm Toán Quận Hai Bà Trưng (Ngõ 230 Lạc Trung – Gần Minh Khai, Times City)
- 🌿 Lớp học thêm Toán tại KĐT Ecopark & Văn Giang (111 Vạn Tuế – Toán Phổ thông & Cambridge)
- 🚀 Lớp luyện thi Toán Đánh giá năng lực HSA, TSA & Chinh phục 9+ Tốt nghiệp THPT
- 🏆 Lớp luyện thi Toán vào lớp 10, Toán Chuyên Ngữ / Chuyên XHNV & Toán Quốc tế Cambridge
- 🆕 Bài Toán Tối Ưu Hoá Thực Tế Đạo Hàm (Toán 12), Tư Duy Định Lượng HSA & Chiến Lược Quy Đổi Điểm Bách Phân Vị
- 🆕 Phương Pháp Gắn Hệ Trục Toạ Độ Không Gian Oxyz, Đọc Hiểu Khoa Học TSA & Công Thức Điểm Xét Tuyển BCA 60–40
- 🆕 TỔNG HỢP CÔNG THỨC & KIẾN THỨC CỐT LÕI TOÁN 7
- 🆕 Lộ trình học chuẩn Toán 7 theo năm học (Chương trình GDPT mới)
- 👉 Xem toàn bộ Kho Đề Thi Giữa Kì, Học Kì & Công Thức Toán Lớp 6–12 →
