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

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

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

Đề bài

Cho đồ thị đầy đủ có 5 đỉnh như Hình 2.9. Tìm những chu trình sơ cấp xuất phát từ đỉnh AA và có: độ dài 4; độ dài 5.

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

Hình 2.9: Đồ thị đầy đủ K5K_5 gồm 5 đỉnh A,B,C,D,EA, B, C, D, E xếp thành ngũ giác (B ở đỉnh trên, A bên trái, C bên phải, E dưới trái, D dưới phải). Mỗi cặp đỉnh được nối với nhau bằng một cạnh (tổng cộng 10 cạnh).

Lời giải

Trong đồ thị đầy đủ K5K_5 với các đỉnh A,B,C,D,EA,B,C,D,E, mỗi cặp đỉnh đều được nối, nên mọi dãy đỉnh phân biệt khép kín đều là một chu trình. Chu trình sơ cấp là chu trình không đi qua đỉnh nào quá một lần (trừ đỉnh đầu trùng đỉnh cuối). Hai chu trình chỉ khác nhau về chiều đi được coi là một.

a) Chu trình sơ cấp độ dài 4 xuất phát từ AA

Chu trình độ dài 4 có 4 cạnh, tức đi qua 4 đỉnh phân biệt: đỉnh AA và 3 đỉnh chọn trong {B,C,D,E}\{B,C,D,E\}. Có C43=4C_4^3 = 4 cách chọn bộ 3 đỉnh, mỗi bộ (cùng với AA) tạo thành (4−1)!2=3\dfrac{(4-1)!}{2} = 3 chu trình. Vậy có 4×3=124 \times 3 = 12 chu trình:

- Qua A,B,C,DA,B,C,D: A ⁣− ⁣B ⁣− ⁣C ⁣− ⁣D ⁣− ⁣AA\!-\!B\!-\!C\!-\!D\!-\!A; A ⁣− ⁣B ⁣− ⁣D ⁣− ⁣C ⁣− ⁣AA\!-\!B\!-\!D\!-\!C\!-\!A; A ⁣− ⁣C ⁣− ⁣B ⁣− ⁣D ⁣− ⁣AA\!-\!C\!-\!B\!-\!D\!-\!A.
- Qua A,B,C,EA,B,C,E: A ⁣− ⁣B ⁣− ⁣C ⁣− ⁣E ⁣− ⁣AA\!-\!B\!-\!C\!-\!E\!-\!A; A ⁣− ⁣B ⁣− ⁣E ⁣− ⁣C ⁣− ⁣AA\!-\!B\!-\!E\!-\!C\!-\!A; A ⁣− ⁣C ⁣− ⁣B ⁣− ⁣E ⁣− ⁣AA\!-\!C\!-\!B\!-\!E\!-\!A.
- Qua A,B,D,EA,B,D,E: A ⁣− ⁣B ⁣− ⁣D ⁣− ⁣E ⁣− ⁣AA\!-\!B\!-\!D\!-\!E\!-\!A; A ⁣− ⁣B ⁣− ⁣E ⁣− ⁣D ⁣− ⁣AA\!-\!B\!-\!E\!-\!D\!-\!A; A ⁣− ⁣D ⁣− ⁣B ⁣− ⁣E ⁣− ⁣AA\!-\!D\!-\!B\!-\!E\!-\!A.
- Qua A,C,D,EA,C,D,E: A ⁣− ⁣C ⁣− ⁣D ⁣− ⁣E ⁣− ⁣AA\!-\!C\!-\!D\!-\!E\!-\!A; A ⁣− ⁣C ⁣− ⁣E ⁣− ⁣D ⁣− ⁣AA\!-\!C\!-\!E\!-\!D\!-\!A; A ⁣− ⁣D ⁣− ⁣C ⁣− ⁣E ⁣− ⁣AA\!-\!D\!-\!C\!-\!E\!-\!A.

b) Chu trình sơ cấp độ dài 5 xuất phát từ AA

Chu trình độ dài 5 có 5 cạnh, đi qua đủ cả 5 đỉnh A,B,C,D,EA,B,C,D,E. Số chu trình là (5−1)!2=242=12\dfrac{(5-1)!}{2} = \dfrac{24}{2} = 12:

- A ⁣− ⁣B ⁣− ⁣C ⁣− ⁣D ⁣− ⁣E ⁣− ⁣AA\!-\!B\!-\!C\!-\!D\!-\!E\!-\!A; A ⁣− ⁣B ⁣− ⁣C ⁣− ⁣E ⁣− ⁣D ⁣− ⁣AA\!-\!B\!-\!C\!-\!E\!-\!D\!-\!A; A ⁣− ⁣B ⁣− ⁣D ⁣− ⁣C ⁣− ⁣E ⁣− ⁣AA\!-\!B\!-\!D\!-\!C\!-\!E\!-\!A;
- A ⁣− ⁣B ⁣− ⁣D ⁣− ⁣E ⁣− ⁣C ⁣− ⁣AA\!-\!B\!-\!D\!-\!E\!-\!C\!-\!A; A ⁣− ⁣B ⁣− ⁣E ⁣− ⁣C ⁣− ⁣D ⁣− ⁣AA\!-\!B\!-\!E\!-\!C\!-\!D\!-\!A; A ⁣− ⁣B ⁣− ⁣E ⁣− ⁣D ⁣− ⁣C ⁣− ⁣AA\!-\!B\!-\!E\!-\!D\!-\!C\!-\!A;
- A ⁣− ⁣C ⁣− ⁣B ⁣− ⁣D ⁣− ⁣E ⁣− ⁣AA\!-\!C\!-\!B\!-\!D\!-\!E\!-\!A; A ⁣− ⁣C ⁣− ⁣B ⁣− ⁣E ⁣− ⁣D ⁣− ⁣AA\!-\!C\!-\!B\!-\!E\!-\!D\!-\!A; A ⁣− ⁣C ⁣− ⁣D ⁣− ⁣B ⁣− ⁣E ⁣− ⁣AA\!-\!C\!-\!D\!-\!B\!-\!E\!-\!A;
- A ⁣− ⁣C ⁣− ⁣E ⁣− ⁣B ⁣− ⁣D ⁣− ⁣AA\!-\!C\!-\!E\!-\!B\!-\!D\!-\!A; A ⁣− ⁣D ⁣− ⁣B ⁣− ⁣C ⁣− ⁣E ⁣− ⁣AA\!-\!D\!-\!B\!-\!C\!-\!E\!-\!A; A ⁣− ⁣D ⁣− ⁣C ⁣− ⁣B ⁣− ⁣E ⁣− ⁣AA\!-\!D\!-\!C\!-\!B\!-\!E\!-\!A.

Kiểm tra: Độ dài 4 dùng 4 đỉnh (44 bộ × 3=12\times\, 3 = 12); độ dài 5 dùng cả 5 đỉnh (4!2=12\tfrac{4!}{2}=12). Mỗi chu trình đều xuất phát và kết thúc tại AA, không lặp đỉnh trung gian.

Đáp số

Độ dài 4: có 12 chu trình sơ cấpĐộ dài 5: có 12 chu trình sơ cấp

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.