Chứng minh rằng đồ thị G ở Hình 19 có ít nhất một chu trình Hamilton
Luyện tập 11 trang 43 chuyên đề Toán lớp 11: Chứng minh rằng đồ thị G ở Hình 19 có ít nhất một chu trình Hamilton.
Đồ 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.
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ị