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.

Quảng cáo
2 câu trả lời 240
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.
Quảng cáo
Bạn cần hỏi gì?
Câu hỏi hot cùng chủ đề
-
Đã trả lời bởi chuyên gia
136473 -
Đã trả lời bởi chuyên gia
73320 -
Đã trả lời bởi chuyên gia
48340
Gửi báo cáo thành công!
