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

Giải Luyện tập 1 trang 42 Chuyên đề Toán 11

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

Đề bài

Đồ thị nào dưới đây có một đường đi Euler? Hãy chỉ ra một đường đi Euler của nó.

Bài có hình vẽ / bảng trong sách — xem ở trang 42 · mở sách.
Hình trong bài (mô tả bằng lời):

Hình 2.19 gồm hai đồ thị:
a) Đồ thị có 5 đỉnh A, B ở hàng trên và C, D, E ở hàng dưới. Các cạnh: A–C, A–D, A–E, B–C, B–D (các cạnh nối chéo tạo hình zic-zắc giữa hai hàng đỉnh).
b) Đồ thị có 4 đỉnh: A ở trên, C và B ở dưới, D ở giữa trong tam giác. Các cạnh: A–C, A–B, C–B, A–D, C–D, D–B (tam giác ABC với D là điểm trong nối tới cả ba đỉnh A, C, B).

Lời giải

Nhắc lại kiến thức (SGK): Một đồ thị liên thông có *đường đi Euler* khi và chỉ khi nó có đúng 00 hoặc 22 đỉnh bậc lẻ.
- Nếu có 00 đỉnh bậc lẻ thì tồn tại *chu trình Euler*.
- Nếu có đúng 22 đỉnh bậc lẻ thì tồn tại *đường đi Euler*, và đường đi đó nhận hai đỉnh bậc lẻ làm điểm đầu và điểm cuối.

a) Xét đồ thị a) với các cạnh AC,AD,AE,BC,BDAC, AD, AE, BC, BD.

Tính bậc của mỗi đỉnh:
- deg⁡(A)=3\deg(A) = 3 (nối với C,D,EC, D, E)
- deg⁡(B)=2\deg(B) = 2 (nối với C,DC, D)
- deg⁡(C)=2\deg(C) = 2 (nối với A,BA, B)
- deg⁡(D)=2\deg(D) = 2 (nối với A,BA, B)
- deg⁡(E)=1\deg(E) = 1 (nối với AA)

Đồ thị liên thông và có đúng hai đỉnh bậc lẻ là AA (bậc 33) và EE (bậc 11). Do đó đồ thị a) có đường đi Euler, với điểm đầu và điểm cuối là hai đỉnh AA và EE.

Một đường đi Euler: xuất phát từ EE, đi lần lượt qua tất cả các cạnh một lần:
E→A→C→B→D→A.E \to A \to C \to B \to D \to A.
Kiểm tra: đường đi dùng các cạnh EA,AC,CB,BD,DAEA, AC, CB, BD, DA — đúng 55 cạnh, mỗi cạnh đúng một lần. Vậy đây là một đường đi Euler (kết thúc tại AA).

b) Xét đồ thị b) là tam giác ABCABC với DD nằm trong nối tới cả ba đỉnh, gồm các cạnh AC,AB,CB,AD,CD,DBAC, AB, CB, AD, CD, DB. Đây chính là đồ thị đầy đủ K4K_4.

Tính bậc của mỗi đỉnh:
- deg⁡(A)=3\deg(A) = 3 (nối với C,B,DC, B, D)
- deg⁡(B)=3\deg(B) = 3 (nối với A,C,DA, C, D)
- deg⁡(C)=3\deg(C) = 3 (nối với A,B,DA, B, D)
- deg⁡(D)=3\deg(D) = 3 (nối với A,C,BA, C, B)

Đồ thị có cả bốn đỉnh đều bậc lẻ, tức là có 44 đỉnh bậc lẻ (nhiều hơn 22). Theo điều kiện trên, đồ thị

b) không có đường đi Euler.

Kết luận: Chỉ có đồ thị a) có đường đi Euler, chẳng hạn E→A→C→B→D→AE \to A \to C \to B \to D \to A.

Đáp số

Đồ thị a) có đường đi Euler: E→A→C→B→D→AE \to A \to C \to B \to D \to AĐồ thị b) không có đường đi Euler (cả 4 đỉnh đều bậc 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.