Bài 2.14 trang 45 Chuyên đề học tập Toán 11 Kết nối tri thức

Giải Chuyên đề Toán 11 Bài 9: Đường đi Euler và đường đi Hamilton - Kết nối tri thức

Bài 2.14 trang 45 Chuyên đề Toán 11: Với giá trị nào của n thì đồ thị đầy đủ K_n có một chu trình Hamilton? Có một đường đi Hamilton?

Quảng cáo

Lời giải:

Đồ thị đầy đủ K_n có n ≥ 2, n ∈ ℕ.

+ Với n = 2 ta có K₂ không có chu trình Hamilton, nhưng có đường đi Hamilton (đi từ đỉnh này qua đỉnh còn lại).

Bài 2.14 trang 45 Chuyên đề học tập Toán 11 Kết nối tri thức

+ Với n ≥ 3, n ∈ ℕ.

Đồ thị đầy đủ K_n 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 K_n 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 K_n có một đường đi Hamilton khi mỗi đỉnh có bậc không nhỏ hơn $\frac{n - 1}{2}$ , tức là n – 1 ≥ $\frac{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 đủ K_n có một chu trình Hamilton và với n ≥ 2, n ∈ ℕ thì đồ thị đầy đủ K_n có một đường đi Hamilton.

Quảng cáo

Lời giải bài tập Chuyên đề Toán 11 Bài 9: Đường đi Euler và đường đi Hamilton hay, chi tiết khác: