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

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 giữa các đỉnh. Lí thuyết đồ thị có nhiều ứng dụng trong khoa học máy tính, kỹ thuật, kinh tế, và nhiều lĩnh vực khác.

2. Đường đi Euler

Một đườ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. Một đồ thị có đường đi Euler khi và chỉ khi nó có tối đa hai đỉnh bậc lẻ. Một đỉnh bậc lẻ là một đỉnh có số cạnh kề lẻ.

2.1. Điều kiện cần và đủ để có đường đi Euler

• Điều kiện cần: Nếu một đồ thị có đường đi Euler, thì nó có tối đa hai đỉnh bậc lẻ.
• Điều kiện đủ: Nếu một đồ thị liên thông có tối đa hai đỉnh bậc lẻ, thì nó có đường đi Euler.

2.2. Thuật toán tìm đường đi Euler

Có nhiều thuật toán để tìm đường đi Euler, một trong số đó 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 thể tiếp tục. Sau đó, nó quay lại các đỉnh đã duyệt và tìm các đường đi khác cho đến khi tất cả các cạnh đều được duyệt qua.

3. Đường đi Hamilton

Một đườ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. Không giống như đường đi Euler, không có điều kiện cần và đủ đơn giản để xác định xem một đồ thị có đường đi Hamilton hay không. Bài toán tìm đường đi Hamilton là một bài toán NP-khó.

3.1. Bài toán người bán hàng du lịch (Traveling Salesman Problem - TSP)

Bài toán người bán hàng du lịch là một ứng dụng nổi tiếng của đường đi Hamilton. Bài toán này yêu cầu tìm một đường đi ngắn nhất đi qua tất cả các thành phố được cho trước và quay trở lại thành phố xuất phát.

3.2. Thuật toán tìm đường đi Hamilton

Do tính NP-khó của bài toán, không có thuật toán hiệu quả nào để tìm đường đi Hamilton cho tất cả các đồ thị. Tuy nhiên, có một số thuật toán heuristic có thể tìm ra các giải pháp gần đúng, chẳng hạn như thuật toán nhánh và cận (branch and bound) và thuật toán di truyền (genetic algorithm).

4. Ví dụ minh họa

Ví dụ 1: Cho một đồ thị có 4 đỉnh A, B, C, D và các cạnh AB, BC, CD, DA. Đồ thị này có đường đi Euler vì tất cả các đỉnh đều có bậc chẵn.

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

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

1. Cho một đồ thị có 5 đỉnh A, B, C, D, E và các cạnh AB, BC, CD, DE, EA. Đồ thị này có đường đi Euler không? Tại sao?
2. Cho một đồ thị 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 Hamilton không? Tại sao?
3. Tìm đường đi Euler (nếu có) cho đồ thị sau: ... (thêm hình ảnh đồ thị)
4. Tìm đường đi Hamilton (nếu có) cho đồ thị sau: ... (thêm hình ảnh đồ thị)

6. Kết luận

Bài học hôm nay đã cung cấp cho các em những kiến thức cơ bản về đường đi Euler và đường đi Hamilton trong lí thuyết đồ thị. Hy vọng rằng các em đã nắm vững kiến thức và có thể áp dụng chúng vào giải quyết các bài toán thực tế. Chúc các em học tập tốt!