Giải Hoạt động 5 trang 38 Chuyên đề Toán 11
Đề bài
Nhận biết khái niệm đường đi và chu trình
Cho đồ thị như Hình 2.7. Bằng cách đi dọc theo các cạnh, với điều kiện không đi qua cạnh nào quá một lần (có thể có cạnh không cần đi qua), hãy chỉ ra các cách để:
a) Đi từ đỉnh đến đỉnh .
b) Đi từ đỉnh và lại quay về đỉnh .
Hình 2.7: Đồ thị có 5 đỉnh A, B, C, D, E. Các cạnh: AB, AD, BC, BD, CD, DE. Đỉnh A ở trên cùng, B bên trái, C ở dưới, D ở giữa bên phải, E ngoài cùng bên phải. B nối với D bằng một cạnh ngang; A nối với B và D tạo tam giác ABD; C nối với B và D tạo tam giác BCD; D nối với E bằng cạnh ngang.
Lời giải
Đồ thị Hình 2.7 có đỉnh và cạnh: .
Bậc của các đỉnh: bậc (kề ); bậc (kề ); bậc (kề ); bậc (kề ); bậc (chỉ kề ).
Quy ước: *đường đi* là dãy các đỉnh và cạnh kề nhau liên tiếp, trong đó không cạnh nào đi quá một lần (đỉnh được phép lặp lại); *chu trình* là một đường đi khép kín (đỉnh đầu trùng đỉnh cuối).
Nhận xét. Đỉnh bậc : muốn tới bắt buộc dùng cạnh và phải đang ở ; vì cạnh chỉ được dùng một lần nên nó luôn là cạnh cuối cùng của mọi đường đi tới .
## a) Các đường đi từ đỉnh đến đỉnh
Mỗi đường đi tới = (một đường đi từ đến chỉ dùng các cạnh ) rồi nối thêm cạnh . Xét hai ngả rẽ đầu tiên từ :
Xuất phát (cạnh ):
- — cạnh .
- — cạnh (đỉnh qua lần nhưng không cạnh nào lặp).
- — cạnh .
Xuất phát (cạnh ):
- — cạnh .
- — cạnh .
Các ngả còn lại đều bế tắc (dùng hết cạnh ở một đỉnh mà chưa tới ). Vậy có đúng đường đi từ đến :
##
b) Các chu trình từ đỉnh quay về đỉnh
Chu trình không thể chứa cạnh : nếu đi tới thì chỉ có cạnh để quay ra, mà cạnh này đã dùng. Do đó chỉ dùng các cạnh .
Đỉnh bậc , nên một chu trình qua phải dùng cả hai cạnh và (một để đi, một để về). Xét hai chiều xuất phát:
Xuất phát (về qua cạnh ):
- — cạnh .
- — cạnh .
Xuất phát (về qua cạnh ):
- — cạnh .
- — cạnh .
Không có chu trình nào dùng cả cạnh , vì khi đó hai đỉnh đều có bậc lẻ () nên không tồn tại đường đi khép kín dùng hết các cạnh đó. (Chẳng hạn không hợp lệ vì cạnh và là một cạnh, bị dùng hai lần.)
Vậy có đúng chu trình từ về :
Trong đó cặp và cặp là cùng một vòng đi theo hai chiều ngược nhau.
Đáp số
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.