Giải bài tập Bài 4 trang 43 Chuyên đề Toán 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 Bài 4 trang 43 Chuyên đề Toán 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:
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.
Đáp án và cách giải chi tiết:
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.
Nguồn: giaitoanhay.com
Tổng số đánh giá:
Xếp hạng: / 5 sao
Loading...