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.

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.

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. (ảnh 1)

Trả lời

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.

Câu hỏi cùng chủ đề

Xem tất cả