Bài 2. Đường đi Euler và đường đi Hamilton

Bài 2. Đường đi Euler và đường đi Hamilton - Chuyên đề Lí thuyết đồ thị - Toán 11 Chân trời sáng tạo

Bài 2 trong chuyên đề Lí thuyết đồ thị của chương trình Toán 11 Chân trời sáng tạo tập trung vào hai khái niệm quan trọng: đường đi Euler và đường đi Hamilton. Đây là những khái niệm nền tảng trong lý thuyết đồ thị, có ứng dụng rộng rãi trong nhiều lĩnh vực như khoa học máy tính, vận tải, và mạng lưới.

1. Giới thiệu chung về đồ thị

Trước khi đi sâu vào đường đi Euler và Hamilton, chúng ta cần ôn lại một số kiến thức cơ bản về đồ thị. Đồ thị là một cấu trúc toán học được sử dụng để mô hình hóa các mối quan hệ giữa các đối tượng. Một đồ thị bao gồm các đỉnh (vertices) và các cạnh (edges) nối giữa các đỉnh.

2. Đường đi Euler

Đường đi Euler là một đường đi trong đồ thị đi qua tất cả các cạnh của đồ thị đúng một lần. Một đồ thị có đường đi Euler khi và chỉ khi:

• Đồ thị liên thông.
• Số đỉnh có bậc lẻ là 0 hoặc 2.

Nếu đồ thị có đúng hai đỉnh có bậc lẻ, thì đường đi Euler bắt đầu từ một trong hai đỉnh đó và kết thúc tại đỉnh còn lại. Nếu đồ thị có tất cả các đỉnh có bậc chẵn, thì đường đi Euler là một chu trình Euler (bắt đầu và kết thúc tại cùng một đỉnh).

3. Đường đi Hamilton

Đường đi Hamilton là một đường đi trong đồ thị đi qua tất cả các đỉnh của đồ thị đúng một lần. Việc xác định một đồ thị có đường đi Hamilton hay không là một bài toán khó hơn nhiều so với việc xác định một đồ thị có đường đi Euler. Không có một điều kiện cần và đủ đơn giản để xác định sự tồn tại của đường đi Hamilton.

4. Thuật toán tìm đường đi Euler và Hamilton

Có nhiều thuật toán khác nhau để tìm đường đi Euler và Hamilton. Một số thuật toán phổ biến bao gồm:

• Thuật toán Fleury: Dùng để tìm đường đi Euler.
• Thuật toán Held-Karp: Dùng để tìm đường đi Hamilton (thuật toán này có độ phức tạp cao).
• Thuật toán nhánh và cận: Dùng để tìm đường đi Hamilton.

5. Ứng dụng của đường đi Euler và Hamilton

Đường đi Euler và Hamilton có nhiều ứng dụng thực tế, bao gồm:

• Bài toán cây cầu Königsberg: Bài toán kinh điển về đường đi Euler, đặt ra bởi Leonhard Euler.
• Bài toán người bán hàng: Bài toán tìm đường đi Hamilton ngắn nhất để đi qua tất cả các thành phố và quay trở lại điểm xuất phát.
• Thiết kế mạng lưới: Tìm đường đi tối ưu trong mạng lưới giao thông hoặc mạng lưới máy tính.

6. Ví dụ minh họa

Ví dụ 1: Cho đồ thị G có 5 đỉnh và 6 cạnh. Xác định xem đồ thị G có đường đi Euler hay không.

Để xác định, ta cần kiểm tra xem đồ thị G có liên thông hay không và số đỉnh có bậc lẻ là 0 hoặc 2. Nếu cả hai điều kiện đều được thỏa mãn, thì đồ thị G có đường đi Euler.

Ví dụ 2: Cho đồ thị G có 4 đỉnh và 4 cạnh. Xác định xem đồ thị G có đường đi Hamilton hay không.

Việc xác định sự tồn tại của đường đi Hamilton trong trường hợp này phức tạp hơn. Ta có thể thử các phương pháp liệt kê hoặc sử dụng các thuật toán tìm kiếm để kiểm tra.

7. Bài tập luyện tập

1. Cho đồ thị G có 6 đỉnh và 7 cạnh. Xác định xem đồ thị G có đường đi Euler hay không.
2. Cho đồ thị G có 5 đỉnh và 5 cạnh. Xác định xem đồ thị G có đường đi Hamilton hay không.
3. Tìm đường đi Euler (nếu có) trong đồ thị G cho trước.
4. Tìm đường đi Hamilton (nếu có) trong đồ thị G cho trước.

Hy vọng bài học này đã cung cấp cho các em những kiến thức cơ bản và hữu ích về đường đi Euler và đường đi Hamilton. Chúc các em học tập tốt!