Câu hỏi:

151 lượt xem
Tự luận

Luyện tập 10 trang 42 chuyên đề Toán lớp 11Chứng minh rằng đồ thị G ở Hình 17 có ít nhất một chu trình Hamilton. 

Luyện tập 10 trang 42 chuyên đề Toán lớp 11 Cánh diều | Giải Chuyên đề Toán 11

Xem đáp án

Lời giải

Hướng dẫn giải:

Ta có: d(A) = 3, d(B) = 4, d(C) = 3, d(E) = 3, d(F) = 3. Đồ thị G ở Hình 17 gồm 5 đỉnh, mỗi đỉnh của đồ thị đều có bậc không nhỏ hơn 52 . Do đó, theo định lí Dirac, đồ thị G có ít nhất một chu trình Hamilton.

CÂU HỎI HOT CÙNG CHỦ ĐỀ