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

Bài 9. Đường đi Euler và đường đi Hamilton - Toán 11 Kết nối tri thức

Bài học này sẽ cung cấp cho các em một cái nhìn tổng quan về lý thuyết đồ thị, tập trung vào hai khái niệm quan trọng là đường đi Euler và đường đi Hamilton. Chúng ta sẽ bắt đầu bằng việc định nghĩa chính xác hai loại đường đi này, sau đó đi sâu vào các điều kiện cần và đủ để một đồ thị có đường đi Euler hoặc đường đi Hamilton.

1. Định nghĩa về Đường đi Euler và Đường đi Hamilton

Đường đi Euler: Là một đường đi trong đồ thị đi qua tất cả các cạnh đúng một lần. Đồ thị có đường đi Euler được gọi là đồ thị Euler.

Đường đi Hamilton: Là một đường đi trong đồ thị đi qua tất cả các đỉnh đúng một lần. Đồ thị có đường đi Hamilton được gọi là đồ thị Hamilton.

2. Điều kiện tồn tại Đường đi Euler

Một đồ thị liên thông có đường đi Euler khi và chỉ khi nó có tối đa hai đỉnh bậc lẻ. Nếu đồ thị có đúng hai đỉnh bậc lẻ, đườ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 bậc chẵn, đườ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. Điều kiện tồn tại Đường đi Hamilton

Việc xác định điều kiện tồn tại đường đi Hamilton phức tạp hơn nhiều so với đường đi Euler. Không có điều kiện cần và đủ đơn giản cho tất cả các đồ thị. Tuy nhiên, có một số định lý và quy tắc có thể giúp chúng ta xác định xem một đồ thị có khả năng có đường đi Hamilton hay không. Ví dụ:

• Nếu một đồ thị có n đỉnh (n ≥ 3) và mỗi đỉnh có bậc lớn hơn hoặc bằng n/2, thì đồ thị đó có đường đi Hamilton.
• Đồ thị đầy đủ (mỗi cặp đỉnh đều được nối với nhau) luôn có đường đi Hamilton.

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

Có nhiều thuật toán khác nhau để tìm đường đi Euler và đường đi Hamilton. Một trong những thuật toán phổ biến nhất để tìm đường đi Euler là thuật toán Hierholzer. Thuật toán này bắt đầu từ một đỉnh bất kỳ và duyệt qua các cạnh của đồ thị cho đến khi không còn cạnh nào chưa được duyệt. Đối với đường đi Hamilton, thuật toán tìm kiếm vét cạn (brute-force) có thể được sử dụng, nhưng nó không hiệu quả đối với các đồ thị lớn.

5. 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ó tất cả các đỉnh bậc 2, do đó nó có một chu trình Euler. Một chu trình Euler có thể là ABCDEA.

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ó tất cả các đỉnh bậc 2, do đó nó có một chu trình Euler. Một chu trình Euler có thể là ABCD.

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

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

• Lập kế hoạch tuyến đường: Tìm tuyến đường ngắn nhất để đi qua tất cả các địa điểm một lần.
• Thiết kế mạch điện: Thiết kế mạch điện sao cho tất cả các linh kiện được kết nối với nhau.
• Bài toán người bán hàng: Tìm tuyến đường ngắn nhất để đi qua tất cả các thành phố một lần và quay trở lại thành phố ban đầu.

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

Để củng cố kiến thức về đường đi Euler và đường đi Hamilton, các em hãy thử giải các bài tập sau:

1. Cho đồ thị G có 6 đỉnh và các cạnh AB, BC, CD, DE, EF, FA. Đồ thị này có đường đi Euler hay đường đi Hamilton?
2. Cho đồ thị G có 5 đỉnh và các cạnh AB, BC, CA, AD, AE. Đồ thị này có đường đi Euler hay đường đi Hamilton?

Hy vọng bài học này đã giúp các em hiểu rõ hơn về đường đi Euler và đường đi Hamilton. Chúc các em học tập tốt!