Giải bài tập Luyện tập 11 trang 43 chuyên đề Toán lớp 11 | Chuyên đề học tập Cánh diều
Hướng dẫn giải chi tiết từng bước bài tập Luyện tập 11 trang 43 chuyên đề Toán lớp 11. Bài 1. Một vài yếu tố của Lí thuyết đồ thị. Đường đi Euler và đường đi Hamilton. Chuyên đề học tập Cánh diều
Đề bài:
Chứng minh rằng đồ thị G ở Hình 19 có ít nhất một chu trình Hamilton.
Đáp án và cách giải chi tiết:
Đồ 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.
Nguồn: giaitoanhay.com
Tổng số đánh giá:
Xếp hạng: / 5 sao
Loading...