Giải bài tập Bài 2.14 trang 45 Chuyên đề Toán 11 | Chuyên đề học tập Kết Nối Tri Thức
Hướng dẫn giải chi tiết từng bước bài tập Bài 2.14 trang 45 Chuyên đề Toán 11. Bài 9. Đường đi Euler và đường đi Hamilton. Chuyên đề học tập Kết Nối Tri Thức
Đề bài:
Bài 2.14 trang 45 Chuyên đề Toán 11: Với giá trị nào của n thì đồ thị đầy đủ Kn có một chu trình Hamilton? Có một đường đi Hamilton?
Đáp án và cách giải chi tiết:
Đồ thị đầy đủ Kn có n ≥ 2, n ∈ ℕ.
+ Với n = 2 ta có K2 không có chu trình Hamilton, nhưng có đường đi Hamilton (đi từ đỉnh này qua đỉnh còn lại).
+ Với n ≥ 3, n ∈ ℕ.
Đồ thị đầy đủ Kn là một đơn đồ thị có n đỉnh và mỗi đỉnh có bậc là n – 1.
- Sử dụng định lí Ore, ta thấy Kn có một chu trình Hamilton khi mỗi cặp đỉnh không kề nhau đều có tổng bậc không nhỏ hơn n, tức là (n – 1) + (n – 1) ≥ n, tương đương với n ≥ 2, kết hợp với điều kiện suy ra n ≥ 3, n ∈ ℕ. (Ta cũng có thể sử dụng định lí Dirac để tìm điều kiện của n)
- Sử dụng Định lí 4 (suy ra từ định lí Dirac), ta thấy Kn có một đường đi Hamilton khi mỗi đỉnh có bậc không nhỏ hơn 
, tức là 
, tương đương với n ≥ 1, kết hợp với điều kiện suy ra n ≥ 3, n ∈ ℕ.
Vậy với n ≥ 3, n ∈ ℕ thì đồ thị đầy đủ Kn có một chu trình Hamilton và với n ≥ 2, n ∈ ℕ thì đồ thị đầy đủ Kn có một đường đi Hamilton.
Nguồn: giaitoanhay.com
Tổng số đánh giá:
Xếp hạng: / 5 sao