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

Trong lĩnh vực toán học rời rạc, đặc biệt là lý thuyết đồ thị, đường đi Euler và đường đi Hamilton là hai khái niệm quan trọng và thú vị. Chúng liên quan đến việc tìm kiếm một đường đi trong đồ thị sao cho đi qua tất cả các cạnh (đường đi Euler) hoặc tất cả các đỉnh (đường đi Hamilton) đúng một lần.

1. Định nghĩa

• Đườ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.
• Đườ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.

2. Điều kiện tồn tại

2.1. Đ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:

• Đồ thị có tối đa hai đỉnh bậc lẻ.
• Nếu có hai đỉnh bậc lẻ, chúng phải là điểm đầu và điểm cuối của đường đi Euler.

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

2.2. Đ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 là một bài toán khó hơn nhiều so với đường đi Euler. Không có điều kiện cần và đủ đơn giản để xác định sự tồn tại của đường đi Hamilton trong một đồ thị bất kỳ. Tuy nhiên, có một số định lý và kết quả liên quan:

• Nếu một đồ thị có một chu trình Hamilton, nó cũng có một đường đi Hamilton.
• Đồ thị đầy đủ (mỗi đỉnh được nối với tất cả các đỉnh khác) luôn có chu trình Hamilton.

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

3.1. Thuật toán Hierholzer (tìm đường đi Euler)

Thuật toán Hierholzer là một thuật toán hiệu quả để tìm đường đi Euler trong một đồ thị. Thuật toán này dựa trên việc duyệt đồ thị một cách đệ quy, bắt đầu từ một đỉnh bất kỳ và đi theo các cạnh chưa được duyệt.

1. Chọn một đỉnh bắt đầu.
2. Duyệt đồ thị từ đỉnh bắt đầu, đi theo các cạnh chưa được duyệt.
3. Khi gặp một đỉnh đã được duyệt, quay lại đỉnh trước đó.
4. Lặp lại quá trình cho đến khi không còn cạnh nào chưa được duyệt.

3.2. Thuật toán Brute-Force (tìm đường đi Hamilton)

Do tính phức tạp của bài toán, thuật toán Brute-Force thường được sử dụng để tìm đường đi Hamilton trong các đồ thị nhỏ. Thuật toán này dựa trên việc thử tất cả các hoán vị có thể của các đỉnh và kiểm tra xem có hoán vị nào tạo thành một đường đi Hamilton hay không.

4. Ví dụ minh họa

Ví dụ 1: Xét đồ thị có các cạnh (1,2), (2,3), (3,4), (4,1). Đồ thị này có chu trình Euler vì tất cả các đỉnh đều có bậc 2 (bậc chẵn).

Ví dụ 2: Xét đồ thị có các cạnh (1,2), (2,3), (3,4). Đồ thị này có đường đi Euler vì có hai đỉnh bậc lẻ (1 và 4).

5. Ứng dụng

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

• Bài toán người bán hàng: Tìm đường đi 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.
• Bài toán định tuyến: Tìm đường đi tối ưu để kết nối các điểm trong một mạng lưới.
• Thiết kế mạch điện: Tìm đường đi ngắn nhất để kết nối các linh kiện trên một bảng mạch.

6. Bài tập thực hành

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

1. Cho một đồ thị có 5 đỉnh. Hãy xác định xem đồ thị này có đường đi Euler hay không.
2. Cho một đồ thị có 6 đỉnh. 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 bạn hiểu rõ hơn về đường đi Euler và đường đi Hamilton. Chúc bạn học tập tốt!