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

Trang trước Trang sau

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?

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.

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:

Xem thêm lời giải bài tập Chuyên đề học tập Toán 11 Kết nối tri thức hay, chi tiết khác:

Trang trước Trang sau

Giải bài tập lớp 11 sách mới các môn học