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.

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 nếu và chỉ nếu nó có tối đa hai đỉnh bậc lẻ. Đỉnh bậc lẻ là đỉ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ì số đỉnh bậc lẻ của đồ thị không vượt quá 2.
• Điều kiện đủ: Nếu một đồ thị liên thông có đúng 0 hoặc 2 đỉ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 cho đến khi không thể tiếp tục. Sau đó, nó quay lại các đỉnh chưa được duyệt và tiếp tục duyệt cho đến khi tất cả các cạnh đều được duyệt.

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.

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 bài toán nổi tiếng trong khoa học máy tính và toán học ứng dụng. Bài toán này yêu cầu tìm đường đi Hamilton ngắn nhất qua một tập hợp các thành phố, sao cho người bán hàng có thể ghé thăm tất cả các thành phố và quay trở lại điểm xuất phát.

3.2. Các phương pháp giải bài toán Hamilton

Bài toán Hamilton là một bài toán NP-khó, nghĩa là không có thuật toán nào được biết đến có thể giải bài toán này trong thời gian đa thức. Tuy nhiên, có nhiều thuật toán heuristic và approximation algorithm có thể tìm ra các giải pháp gần đúng.

4. Ví dụ minh họa

Ví dụ 1: Cho đồ thị G 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 vì tất cả các đỉnh đều có bậc chẵn.

Ví dụ 2: Cho đồ thị G có 4 đỉnh A, B, C, D và các cạnh AB, BC, CD, DA. Đồ thị này có đườ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

• Lập kế hoạch tuyến đường: Tìm tuyến đường ngắn nhất để ghé thăm tất cả các địa điểm.
• Thiết kế mạch điện: Tìm cách kết nối tất cả các linh kiện điện tử trên một bảng mạch.
• Phân tích mạng lưới giao thông: Tìm cách tối ưu hóa luồng giao thông trên một mạng lưới đường xá.

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

1. Cho đồ thị G có 6 đỉnh và các cạnh sau: AB, AC, AD, BC, BD, CD. Hãy xác định xem đồ thị này có đường đi Euler hay không?
2. Cho đồ thị G có 5 đỉnh và các cạnh sau: AB, BC, CD, DE, EA. Hãy xác định xem đồ thị này có đường đi Hamilton hay không?

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!