Giải Thực hành 3 Bài 2. Đường đi Euler và đường đi Hamilton (trang 54, 55, 56, 57, 58) – Chuyên đề học tập Toán 11 Chân trời sáng tạo. Hướng dẫn: Trong đồ thị, một đường đi được gọi là đường đi Hamilton nếu đường đi đó đi qua tất cả.
Câu hỏi/Đề bài:
Hãy chỉ ra rằng mỗi đồ thị sau đây có chu trình Hamilton.
Hướng dẫn:
Trong đồ thị, một đường đi được gọi là đường đi Hamilton nếu đường đi đó đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng 1 lần.
Nếu chu trình là đường đi Hamilton thì chu trình đó được gọi là chu trình Hamilton.
Lời giải:
⦁ Hình 21a:
Đồ thị ở Hình 21a có các đỉnh A, F có bậc 2.
Suy ra chu trình Hamilton h (nếu có) phải đi qua các cạnh AB, AD, FD, FC trong đồ thị ở Hình 21a.
Do đó h không thể đi qua các cạnh BD, DC.
Nếu xóa đi hai cạnh này thì đỉnh B, C trở thành có bậc 2.
Vì vậy h phải đi qua cạnh BC.
Khi đó ta được chu trình Hamilton h: ADFCBA.
⦁ Hình 21b:
Đồ thị ở Hình 21b có các đỉnh F, I có bậc 2.
Suy ra chu trình Hamilton h (nếu có) phải đi qua các cạnh FE, FB, IA, IC.
Do đó ta được chu trình Hamilton h: AICBFEDA (hoặc AICDEFBA).
Vậy cả hai đồ thị đã cho đều có chu trình Hamilton.