Câu hỏi:
96 lượt xemBà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?
Lời giải
Hướng dẫn giải:
Đồ 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 \(\dfrac{n-1}{2}\), tức là n – 1 ≥ \(\dfrac{n-1}{2}\), 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.
ĐỀ THI LIÊN QUAN:
-
34 câu hỏi 70 lượt thi