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

Với giá trị nào của n thì đồ thị đầy đủ Kn có một chu trình Euler? Có một đường đi Euler?

Đề bài

Với giá trị nào của n thì đồ thị đầy đủ K_n có một chu trình Euler? Có một đường đi Euler?

Phương pháp giải - Xem chi tiết

Trong đồ thị, một đường đi được gọi là đường đi Euler nếu đường đi đó đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng 1 lần.

Nếu chu trình là đường đi Euler thì chu trình đo được gọi là chu trình Euler.

Lời giải chi tiết

Đồ thị đầy đủ \({K_n}\) có \(n{\rm{ }} \ge {\rm{ }}2,{\rm{ }}n\; \in \;\mathbb{N}.\)

Đồ thị đầy đủ \({K_n}\) là đồ thị liên thông.

Mỗi đỉnh của \({K_n}\) đều có bậc là n – 1.

+) Theo định lí Euler, K_n có chu trình Euler khi K_n liên thông (đã thỏa mãn) và mọi đỉnh của K_n đều có bậc chẵn, điều này có nghĩa để K_n có một chu trình Euler thì n – 1 phải là số chẵn hay n phải là số lẻ, tức là \(n{\rm{ }} = {\rm{ }}2k{\rm{ }} + {\rm{ }}1{\rm{ }}(k\; \in \;{\mathbb{N}^*}).\) Vậy với \(\;n{\rm{ }} = {\rm{ }}2k{\rm{ }} + {\rm{ }}1{\rm{ }}(k\; \in \;{\mathbb{N}^*})\) thì đồ thị đầy đủ K_n có một chu trình Euler.

+) Đồ thị K_n có một đường đi Euler từ A đến B khi và chỉ khi K_n liên thông và mọi đỉnh của K_n đều có bậc chẵn, chỉ trừ A và B có bậc lẻ. Mà mọi đỉnh của K_n đều có bậc là n – 1, nghĩa là mọi đỉnh của K_n đều có bậc chẵn hoặc đều có bậc lẻ.

- Với n = 2, ta có K₂ có 2 đỉnh đều có bậc là 1 (là bậc lẻ) nên ta có đường đi Euler từ đỉnh này qua đỉnh còn lại.

- Với n > 2, n ∈ ℕ^* thì mọi đỉnh của K_n đều có bậc cùng chẵn hoặc cùng lẻ lớn hơn 2, do đó không thỏa mãn điều kiện để K_n có đường đi Euler.

Vậy đồ thị đầy đủ K_ncó một đường đi Euler khi n = 2.