Trả lời Luyện tập 11 Bài 1. Một vài yếu tố của Lí thuyết đồ thị. Đường đi Euler và đường đi Hamilton (trang 40, 41, 42, 43) – Chuyên đề học tập Toán 11 Cánh diều. Gợi ý: 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:
Chứng minh rằng đồ thị G ở Hình 19 có ít nhất một 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 đinht 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:
Đồ thị G ở Hình 19 gồm 6 đỉnh, trong đó các đỉnh A, D, E có bậc 4, các đỉnh B, C có bậc 5 và đỉnh F có bậc 2 nên tổng bậc của hai đỉnh không kề nhau bất kì đều không nhỏ hơn 6. Do đó, theo định lí Ore, đồ thị G có ít nhất một chu trình Hamilton.