Thực hành 3 trang 57 Chuyên đề Toán 11 Chân trời sáng tạo
Giải Chuyên đề Toán 11 Bài 2: Đường đi Euler và đường đi Hamilton - Chân trời sáng tạo
Thực hành 3 trang 57 Chuyên đề Toán 11: Hãy chỉ ra rằng mỗi đồ thị sau đây có 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.
Lời giải Chuyên đề Toán 11 Bài 2: Đường đi Euler và đường đi Hamilton hay, chi tiết khác:
