Toán lớp 11: Bài 9: Đường đi Euler và đường đi Hamilton

Mục tiêu bài học

• Giải thích và vận dụng đường đi Euler trong một tình huống mới.
• Giải thích và vận dụng chu trình Euler trong một tình huống mới.
• Giải thích và vận dụng đường đi Hamilton trong một tình huống mới.
• Giải thích và vận dụng phân biệt Euler–Hamilton trong một tình huống mới.

Kiến thức cần nhớ

• đường đi Euler: Đường đi Euler đi qua mỗi cạnh đúng một lần.
• chu trình Euler: Chu trình Euler là đường đi Euler khép kín.
• đường đi Hamilton: Đường đi Hamilton thăm mỗi đỉnh đúng một lần.
• phân biệt Euler–Hamilton: Euler kiểm soát cạnh; Hamilton kiểm soát đỉnh.

Khởi động và dự đoán

• Quan sát tình huống, dự đoán đại lượng bất biến rồi ghi lại lý do.

Thuật ngữ và kí hiệu

đường đi Euler chu trình Euler đường đi Hamilton phân biệt Euler–Hamilton

Công thức, điều kiện và ý nghĩa

Biểu thức	Điều kiện	Ý nghĩa
Đường đi Euler đi qua mỗi cạnh đúng một lần.	Đánh dấu cạnh đã dùng, không chỉ đỉnh.	Tìm đường đi dùng mỗi cạnh đúng một lần.
Chu trình Euler là đường đi Euler khép kín.	Kiểm tra liên thông và mọi bậc chẵn.	Giải thích điều kiện bậc cho tuyến quét đường khép kín.
Đường đi Hamilton thăm mỗi đỉnh đúng một lần.	Theo dõi danh sách đỉnh đã thăm.	Tìm thứ tự thăm các điểm mà không lặp đỉnh.
Euler kiểm soát cạnh; Hamilton kiểm soát đỉnh.	Hỏi đối tượng cần dùng đúng một lần là cạnh hay đỉnh.	Phân loại hai bài toán tuyến đường theo Euler/Hamilton.

Tự kiểm tra kiến thức nền

• Đọc đúng kí hiệu, đơn vị và dữ kiện đã cho.
• Phân biệt định nghĩa với tính chất suy ra.
• Nêu điều kiện trước khi thay số hoặc kết luận.
• Tự kiểm tra bằng một cách biểu diễn khác khi có thể.

Khung lập luận và chứng minh

• Ghi giả thiết và kết luận bằng kí hiệu rõ ràng.
• Chọn định nghĩa/tính chất đúng và nêu điều kiện áp dụng.
• Tách từng bước suy luận, không suy từ hình vẽ không tỉ lệ.
• Kiểm tra kết quả bằng dữ kiện độc lập hoặc trường hợp biên.

Trường hợp biên cần nhớ

• Euler quan tâm dùng cạnh; Hamilton quan tâm thăm đỉnh.
• Điều kiện bậc phải được phát biểu đúng cho đồ thị liên thông.

Phản ví dụ chống học máy móc

• Phản ví dụ/biên cần kiểm: Euler quan tâm dùng cạnh; Hamilton quan tâm thăm đỉnh.
• Phản ví dụ/biên cần kiểm: Điều kiện bậc phải được phát biểu đúng cho đồ thị liên thông.

Ứng dụng và mô hình thực tế

• Tìm đường đi dùng mỗi cạnh đúng một lần.
• Giải thích điều kiện bậc cho tuyến quét đường khép kín.
• Tìm thứ tự thăm các điểm mà không lặp đỉnh.
• Phân loại hai bài toán tuyến đường theo Euler/Hamilton.

Minh họa trực quan

Đồ thị đỉnh–cạnh

Theo dõi đỉnh và cạnh bằng nhãn, không tạo đỉnh tại giao điểm không đánh dấu.

Ví dụ giải từng bước

Ví dụ 1 — đường đi Euler

Đồ thị liên thông có đúng hai đỉnh bậc lẻ có đường đi Euler không?

1. 1 Dữ kiện cần dùng: Đường đi Euler đi qua mỗi cạnh đúng một lần.
2. 2 Thực hiện phép tính hoặc đối chiếu đúng quy ước; kết quả trung gian dẫn tới có.
3. 3 Kết luận: có. Tự kiểm: Đánh dấu cạnh đã dùng, không chỉ đỉnh.

Đáp án: có

Tự kiểm: Đánh dấu cạnh đã dùng, không chỉ đỉnh.

Ví dụ 2 — chu trình Euler

Đồ thị liên thông mọi đỉnh bậc chẵn có chu trình Euler không?

1. 1 Dữ kiện cần dùng: Chu trình Euler là đường đi Euler khép kín.
2. 2 Thực hiện phép tính hoặc đối chiếu đúng quy ước; kết quả trung gian dẫn tới có.
3. 3 Kết luận: có. Tự kiểm: Kiểm tra liên thông và mọi bậc chẵn.

Đáp án: có

Tự kiểm: Kiểm tra liên thông và mọi bậc chẵn.

Ví dụ 3 — đường đi Hamilton

Đường Hamilton trong đồ thị 6 đỉnh chứa bao nhiêu đỉnh phân biệt?

1. 1 Dữ kiện cần dùng: Đường đi Hamilton thăm mỗi đỉnh đúng một lần.
2. 2 Thực hiện phép tính hoặc đối chiếu đúng quy ước; kết quả trung gian dẫn tới 6.
3. 3 Kết luận: 6. Tự kiểm: Theo dõi danh sách đỉnh đã thăm.

Đáp án: 6

Tự kiểm: Theo dõi danh sách đỉnh đã thăm.

Ví dụ 4 — phân biệt Euler–Hamilton

Bài toán giao thư ghé mỗi địa điểm một lần thuộc loại nào?

1. 1 Dữ kiện cần dùng: Euler kiểm soát cạnh; Hamilton kiểm soát đỉnh.
2. 2 Thực hiện phép tính hoặc đối chiếu đúng quy ước; kết quả trung gian dẫn tới Hamilton.
3. 3 Kết luận: Hamilton. Tự kiểm: Hỏi đối tượng cần dùng đúng một lần là cạnh hay đỉnh.

Đáp án: Hamilton

Tự kiểm: Hỏi đối tượng cần dùng đúng một lần là cạnh hay đỉnh.

Lỗi sai thường gặp

• Sai: Đi qua mỗi đỉnh đúng một lần. Cách sửa: Đánh dấu cạnh đã dùng, không chỉ đỉnh.
• Sai: Phải quay về đỉnh đầu. Cách sửa: Đánh dấu cạnh đã dùng, không chỉ đỉnh.
• Sai: Được bỏ cạnh. Cách sửa: Đánh dấu cạnh đã dùng, không chỉ đỉnh.
• Sai: Có đúng hai đỉnh bậc lẻ. Cách sửa: Kiểm tra liên thông và mọi bậc chẵn.
• Sai: Không cần dùng mọi cạnh. Cách sửa: Kiểm tra liên thông và mọi bậc chẵn.
• Sai: Chỉ đi mỗi đỉnh một lần. Cách sửa: Kiểm tra liên thông và mọi bậc chẵn.
• Sai: Dùng mỗi cạnh đúng một lần. Cách sửa: Theo dõi danh sách đỉnh đã thăm.
• Sai: Phải dùng mọi cạnh. Cách sửa: Theo dõi danh sách đỉnh đã thăm.