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

Giải Hoạt động 5 trang 38 Chuyên đề Toán 11

Bài 8. Một vài khái niệm cơ bản   Đã kiểm

Đề 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 AA đến đỉnh EE.

b) Đi từ đỉnh AA và lại quay về đỉnh AA.

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

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ó 55 đỉnh A, B, C, D, EA,\ B,\ C,\ D,\ E và 66 cạnh: AB, AD, BC, BD, CD, DEAB,\ AD,\ BC,\ BD,\ CD,\ DE.

Bậc của các đỉnh: AA bậc 22 (kề B, DB,\ D); BB bậc 33 (kề A, C, DA,\ C,\ D); CC bậc 22 (kề B, DB,\ D); DD bậc 44 (kề A, B, C, EA,\ B,\ C,\ E); EE bậc 11 (chỉ kề DD).

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 EE bậc 11: muốn tới EE bắt buộc dùng cạnh DEDE và phải đang ở DD; vì cạnh DEDE 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 EE.

## a) Các đường đi từ đỉnh AA đến đỉnh EE

Mỗi đường đi tới EE = (một đường đi từ AA đến DD chỉ dùng các cạnh AB, AD, BC, BD, CDAB,\ AD,\ BC,\ BD,\ CD) rồi nối thêm cạnh DEDE. Xét hai ngả rẽ đầu tiên từ AA:

Xuất phát A→DA\to D (cạnh ADAD):

- A→D→EA\to D\to E — cạnh AD, DEAD,\ DE.
- A→D→B→C→D→EA\to D\to B\to C\to D\to E — cạnh AD, BD, BC, CD, DEAD,\ BD,\ BC,\ CD,\ DE (đỉnh DD qua 22 lần nhưng không cạnh nào lặp).
- A→D→C→B→D→EA\to D\to C\to B\to D\to E — cạnh AD, CD, BC, BD, DEAD,\ CD,\ BC,\ BD,\ DE.

Xuất phát A→BA\to B (cạnh ABAB):

- A→B→D→EA\to B\to D\to E — cạnh AB, BD, DEAB,\ BD,\ DE.
- A→B→C→D→EA\to B\to C\to D\to E — cạnh AB, BC, CD, DEAB,\ BC,\ CD,\ DE.

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 EE). Vậy có đúng 55 đường đi từ AA đến EE:

A−D−E;A−B−D−E;A−B−C−D−E;A−D−B−C−D−E;A−D−C−B−D−E.A{-}D{-}E;\quad A{-}B{-}D{-}E;\quad A{-}B{-}C{-}D{-}E;\quad A{-}D{-}B{-}C{-}D{-}E;\quad A{-}D{-}C{-}B{-}D{-}E.

##

b) Các chu trình từ đỉnh AA quay về đỉnh AA

Chu trình không thể chứa cạnh DEDE: nếu đi tới EE thì chỉ có cạnh DEDE để quay ra, mà cạnh này đã dùng. Do đó chỉ dùng các cạnh AB, AD, BC, BD, CDAB,\ AD,\ BC,\ BD,\ CD.

Đỉnh AA bậc 22, nên một chu trình qua AA phải dùng cả hai cạnh ABAB và ADAD (một để đi, một để về). Xét hai chiều xuất phát:

Xuất phát A→BA\to B (về AA qua cạnh ADAD):

- A→B→D→AA\to B\to D\to A — cạnh AB, BD, ADAB,\ BD,\ AD.
- A→B→C→D→AA\to B\to C\to D\to A — cạnh AB, BC, CD, ADAB,\ BC,\ CD,\ AD.

Xuất phát A→DA\to D (về AA qua cạnh ABAB):

- A→D→B→AA\to D\to B\to A — cạnh AD, BD, ABAD,\ BD,\ AB.
- A→D→C→B→AA\to D\to C\to B\to A — cạnh AD, CD, BC, ABAD,\ CD,\ BC,\ AB.

Không có chu trình nào dùng cả 55 cạnh AB, AD, BC, BD, CDAB,\ AD,\ BC,\ BD,\ CD, vì khi đó hai đỉnh B, DB,\ D đều có bậc lẻ (=3=3) 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 A→D→B→C→D→AA\to D\to B\to C\to D\to A không hợp lệ vì cạnh ADAD và DADA là một cạnh, bị dùng hai lần.)

Vậy có đúng 44 chu trình từ AA về AA:

A−B−D−A;A−D−B−A;A−B−C−D−A;A−D−C−B−A.A{-}B{-}D{-}A;\quad A{-}D{-}B{-}A;\quad A{-}B{-}C{-}D{-}A;\quad A{-}D{-}C{-}B{-}A.

Trong đó cặp (1,2)(1,2) và cặp (3,4)(3,4) là cùng một vòng đi theo hai chiều ngược nhau.

Đáp số

5 đường đi từ AA đến EE: A−D−EA{-}D{-}E; A−B−D−EA{-}B{-}D{-}E; A−B−C−D−EA{-}B{-}C{-}D{-}E; A−D−B−C−D−EA{-}D{-}B{-}C{-}D{-}E; A−D−C−B−D−EA{-}D{-}C{-}B{-}D{-}E4 chu trình từ AA về AA: A−B−D−AA{-}B{-}D{-}A; A−D−B−AA{-}D{-}B{-}A; A−B−C−D−AA{-}B{-}C{-}D{-}A; A−D−C−B−AA{-}D{-}C{-}B{-}A

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.