Chuyên đề học tập Toán 11

Giải Bài 2.13 trang 45 Chuyên đề Toán 11

Bài 9. Đường đi Euler và đường đi Hamilton   Đã kiểm chéo

Đề bài

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

Lời giải

Trong đồ thị đầy đủ KnK_n (n≥2n \ge 2), mỗi đỉnh nối với tất cả n−1n-1 đỉnh còn lại, nên mọi đỉnh đều có bậc d=n−1d = n-1. Hơn nữa KnK_n luôn là đồ thị liên thông. Ta dùng định lí Euler trong SGK:

- KnK_n có chu trình Euler ⇔\Leftrightarrow KnK_n liên thông và *mọi đỉnh đều có bậc chẵn*.
- KnK_n có đường đi Euler (hở, không phải chu trình) ⇔\Leftrightarrow KnK_n liên thông và có *đúng hai đỉnh bậc lẻ*.

a) Khi nào KnK_n có một chu trình Euler?

Điều kiện: mọi đỉnh có bậc chẵn, tức là
n−1 chẵn  ⇔  n lẻ.n-1 \text{ chẵn} \;\Leftrightarrow\; n \text{ lẻ}.
Để đồ thị thực sự có cạnh (có chu trình) thì cần n≥3n \ge 3.

Vậy KnK_n có chu trình Euler khi và chỉ khi nn lẻ và n≥3n \ge 3 (ví dụ K3,K5,K7,…K_3, K_5, K_7, \dots).

b) Khi nào KnK_n có một đường đi Euler?

Mọi đỉnh của KnK_n đều cùng bậc n−1n-1, nên chỉ có hai khả năng:

- Nếu n−1n-1 chẵn (nn lẻ): tất cả các đỉnh bậc chẵn ⇒\Rightarrow KnK_n có chu trình Euler, và chu trình đó đồng thời là một đường đi Euler.
- Nếu n−1n-1 lẻ (nn chẵn): cả nn đỉnh đều có bậc lẻ. Để tồn tại đường đi Euler (hở) cần đúng 2 đỉnh bậc lẻ, tức là
n=2.n = 2.

Khi n=2n=2: K2K_2 chỉ gồm một cạnh nối hai đỉnh, đường đi qua cạnh đó chính là một đường đi Euler (hở).

Vậy:
- KnK_n có đường đi Euler hở (không khép kín) khi và chỉ khi n=2n = 2.
- Nói chung, KnK_n có đường đi Euler (kể cả trường hợp là chu trình Euler) khi n=2n = 2 hoặc nn lẻ (n≥3n \ge 3).

Kiểm tra lại: K3K_3 (tam giác) mỗi đỉnh bậc 22 (chẵn) ⇒\Rightarrow có chu trình Euler: đúng. K4K_4 mỗi đỉnh bậc 33 (lẻ), có 44 đỉnh bậc lẻ >2⇒> 2 \Rightarrow không có cả chu trình lẫn đường đi Euler: phù hợp. K2K_2 có 22 đỉnh bậc lẻ ⇒\Rightarrow có đường đi Euler hở: phù hợp.

Đáp số

Chu trình Euler: khi nn lẻ và n≥3n \ge 3 (tức n−1n-1 chẵn)Đường đi Euler hở: chỉ khi n=2n = 2 (gộp cả chu trình: n=2n = 2 hoặc nn lẻ)

Lời giải do Thư viện nhà trường biên soạn, giải và kiểm chéo độc lập theo SGK 2026-2027.