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

Bài 9. Đường đi Euler và đường đi Hamilton - Chuyên đề học tập Toán 11 - Kết nối tri thức

1. Giới thiệu chung về Lí thuyết đồ thị

Lí thuyết đồ thị là một nhánh của toán học rời rạc, nghiên cứu về các đồ 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. Nó bao gồm các đỉnh (vertices) và các cạnh (edges) nối các đỉnh này lại với nhau.

Lí thuyết đồ thị có nhiều ứng dụng trong các lĩnh vực khác nhau như khoa học máy tính, mạng máy tính, giao thông vận tải, sinh học, hóa học và kinh tế.

2. Đường đi Euler

Định nghĩa: Đường đi Euler trong một đồ thị là một đường đi đi qua tất cả các cạnh của đồ thị đúng một lần.

Điều kiện cần và đủ để một đồ thị có đường đi Euler:

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

Nếu số đỉnh có bậc lẻ bằng 0, đồ thị có một chu trình Euler (đường đi Euler bắt đầu và kết thúc tại cùng một đỉnh). Nếu số đỉnh có bậc lẻ bằng 2, đồ thị có một đường đi Euler (đường đi Euler bắt đầu và kết thúc tại hai đỉnh khác nhau).

3. Đường đi Hamilton

Định nghĩa: Đường đi Hamilton trong một đồ thị là một đường đi đi qua tất cả các đỉnh của đồ thị đúng một lần.

Điều kiện cần và đủ để một đồ thị có đường đi Hamilton:

Việc xác định điều kiện cần và đủ để một đồ thị có đường đi Hamilton là một bài toán khó trong lí thuyết đồ thị. Không có một điều kiện đơn giản nào đảm bảo rằng một đồ thị có đường đi Hamilton. Tuy nhiên, có một số định lý và thuật toán có thể giúp chúng ta tìm kiếm đường đi Hamilton trong một đồ thị.

4. Ví dụ minh họa

Ví dụ 1: Xét đồ thị G có 5 đỉnh A, B, C, D, E và các cạnh AB, BC, CD, DE, EA. Đồ thị này có một chu trình Euler vì tất cả các đỉnh đều có bậc 2.

Ví dụ 2: Xét đồ thị G có 4 đỉnh A, B, C, D và các cạnh AB, BC, CD, DA. Đồ thị này có một đường đi Hamilton vì nó đi qua tất cả các đỉnh đúng một lần.

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

Ứng dụng của Đường đi Euler:

• Bài toán cầu Königsberg: Bài toán nổi tiếng về việc đi qua tất cả các cầu của thành phố Königsberg đúng một lần.
• Thiết kế mạch điện: Tìm đường đi ngắn nhất để kết nối tất cả các linh kiện trong một mạch điện.

Ứng dụng của Đường đi Hamilton:

• Bài toán người bán hàng: Tìm đường đi ngắn nhất để ghé thăm tất cả các thành phố và quay trở lại điểm xuất phát.
• Lập kế hoạch sản xuất: Sắp xếp thứ tự các công đoạn sản xuất để tối ưu hóa thời gian và chi phí.

6. Bài tập vận dụng

1. Cho đồ thị G có 6 đỉnh A, B, C, D, E, F và các cạnh AB, BC, CD, DE, EF, FA. Đồ thị này có đường đi Euler hay không? Giải thích.
2. Cho đồ thị G có 5 đỉnh A, B, C, D, E và các cạnh AB, BC, CD, DE, EA, AC. Đồ thị này có đường đi Hamilton hay không? Giải thích.

7. Kết luận

Bài học hôm nay đã giúp chúng ta hiểu rõ hơn về Đường đi Euler và Đường đi Hamilton trong lí thuyết đồ thị. Đây là những khái niệm quan trọng và có nhiều ứng dụng thực tế. Hy vọng rằng các em học sinh sẽ nắm vững kiến thức này và áp dụng nó vào giải quyết các bài toán thực tế.