Tìm bậc của mỗi đỉnh và chỉ ra một chu trình Hamilton (nếu có) của đồ thị ở Hình 21
Bài 4 trang 43 Chuyên đề Toán 11: Tìm bậc của mỗi đỉnh và chỉ ra một chu trình Hamilton (nếu có) của đồ thị ở Hình 21.
Ta có: d(A) = 3, d(B) = 3, d(C) = 4, d(D) = 4, d(E) = 2.
Vì đồ thị ở Hình 21 gồm có 5 đỉnh nên tổng bậc của hai đỉnh không kề nhau bất kì đều không nhỏ hơn 5. Do đó, theo định lí Ore, đồ thị này có ít nhất một chu trình Hamilton.
Một chu trình Hamilton của đồ thị này là ABCEDA.
Xem thêm các bài giải Chuyên đề Toán lớp 11 Cánh diều hay, chi tiết khác:
Bài 1: Một vài yếu tố của lí thuyết đồ thị. Đường đi Euler và đường đi Hamilton
Bài 2: Một vài ứng dụng của lí thuyết đồ thị