Giải luyện tập, vận dụng 11 trang 43 Chuyên đề Toán 11 Cánh diều

Luyện tập, vận dụng 11: Chứng minh rằng đồ thị G ở Hình 19 có ít nhất một chu trình Hamilton.

Chứng minh rằng đồ thị G ở Hình 19 có ít nhất một chu trình Hamilton.


Đồ thị G gồm 6 đỉnh, trong đó: d(A) = 4, d(C) = 5

Mà d(A) + d(C) = 9 $> $ 6

Do đó, theo định lí Ore, đồ thị G ở Hình 19 có ít nhất một chu trình Hamilton.


Bình luận

Giải bài tập những môn khác