Bài 8. Một vài khái niệm cơ bản Đã kiểm chéo
Lời giải
Trong đồ thị đầy đủ với các đỉnh , 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ừ
Chu trình độ dài 4 có 4 cạnh, tức đi qua 4 đỉnh phân biệt: đỉnh và 3 đỉnh chọn trong . Có cách chọn bộ 3 đỉnh, mỗi bộ (cùng với ) tạo thành chu trình. Vậy có chu trình:
- Qua : ; ; .
- Qua : ; ; .
- Qua : ; ; .
- Qua : ; ; .
b) Chu trình sơ cấp độ dài 5 xuất phát từ
Chu trình độ dài 5 có 5 cạnh, đi qua đủ cả 5 đỉnh . Số chu trình là :
- ; ; ;
- ; ; ;
- ; ; ;
- ; ; .
Kiểm tra: Độ dài 4 dùng 4 đỉnh ( bộ ); độ dài 5 dùng cả 5 đỉnh (). Mỗi chu trình đều xuất phát và kết thúc tại , không lặp đỉnh trung gian.
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.