Bỏ qua tới nội dung chính
Toán học

Hướng dẫn học chủ đề

Tổ hợp và lý thuyết đồ thị

Trung bìnhkhoảng 42 giờ6 bước

Nguyên lý đếm, hàm sinh, bao hàm – loại trừ, đồ thị, cây, tô màu, luồng và ghép cặp.

Bắt đầu học

Bạn sẽ học được gì

  • Giải bài toán đếm bằng hoán vị, tổ hợp, hệ số đa thức và chứng minh tổ hợp
  • Áp dụng nguyên lý Dirichlet và nguyên lý bao hàm – loại trừ, kể cả để đếm toàn ánh và hoán vị lệch
  • Dùng hàm sinh thường và hàm sinh mũ để giải bài toán đếm và phân hoạch số nguyên
  • Giải hệ thức truy hồi tuyến tính hệ số hằng, thuần nhất và không thuần nhất
  • Chứng minh các tính chất về đồ thị Euler, Hamilton, đồ thị phẳng, tô màu và cây
  • Cài đặt và chứng minh tính đúng của các thuật toán cây khung nhỏ nhất, đường đi ngắn nhất và luồng cực đại
  • Áp dụng định lý luồng cực đại – lát cắt cực tiểu cho bài toán ghép cặp trên đồ thị hai phía
  • Nêu được ý tưởng của lý thuyết Ramsey, phương pháp xác suất và định lý đếm Pólya

Nên học trước

Giới thiệu

Tổ hợp và lý thuyết đồ thị là phần "chuyên sâu" của toán rời rạc: nếu Toán rời rạc dạy những công cụ đếm và khái niệm đồ thị cơ bản, thì môn này dạy cách giải những bài toán đếm khó hơn nhiều, cách chứng minh các định lý cấu trúc về đồ thị và cách tìm lời giải tối ưu cho các bài toán rời rạc lớn. Đây là lĩnh vực vừa có những bài toán phát biểu được cho học sinh phổ thông, vừa có những câu hỏi mở làm đau đầu các nhà toán học hàng đầu — và là nền toán học của tối ưu tổ hợp, thiết kế thuật toán và khoa học mạng. Tương ứng ở MIT là 18.211 Combinatorial Analysis, ở UC Berkeley là Math 172, ở ĐHBK Hà Nội là các môn Toán rời rạc và Tối ưu tổ hợp.

Phần tổ hợp đếm

  • Xâu, tập hợp và hệ số nhị thức: hoán vị, tổ hợp, hệ số đa thức, chứng minh tổ hợp; nhắc lại quy nạp và giải bài toán tổ hợp bằng đệ quy.
  • Nguyên lý chuồng bồ câu (nguyên lý Dirichlet) và nguyên lý bao hàm – loại trừ: đếm toàn ánh, bài toán hoán vị lệch (derangement), hàm phi Euler.
  • Hàm sinh: biến một dãy số thành một chuỗi lũy thừa hình thức để giải bài toán đếm bằng đại số — định lý nhị thức Newton tổng quát, phân hoạch số nguyên, hàm sinh mũ.
  • Hệ thức truy hồi: giải hệ thức tuyến tính hệ số hằng một cách hệ thống (phương pháp toán tử tiến, nghiệm bội) và bằng hàm sinh.

Phần lý thuyết đồ thị

  • Cấu trúc: đồ thị Euler và Hamilton, tô màu, sắc số và clique, đồ thị hai phía, đồ thị phẳng, đếm cây có gán nhãn (công thức Cayley).
  • Thuật toán: cây khung nhỏ nhất (Kruskal, Prim), đường đi ngắn nhất (Dijkstra) trên đồ thị có hướng có trọng số.
  • Luồng trên mạng: luồng và lát cắt, đường tăng luồng, thuật toán Ford–Fulkerson, định lý luồng cực đại – lát cắt cực tiểu, và ứng dụng tổ hợp: ghép cặp trên đồ thị hai phía, phân hoạch thành xích.

Những ý tưởng đẹp để kết thúc

Hai chủ đề cuối cho thấy sự sâu sắc của tổ hợp hiện đại: lý thuyết Ramsey ("trong mọi nhóm 6 người luôn có 3 người đôi một quen nhau hoặc 3 người đôi một không quen nhau") cùng phương pháp xác suất của Erdős — chứng minh một đối tượng tồn tại bằng cách chỉ ra xác suất chọn ngẫu nhiên được nó là dương; và định lý đếm Pólya, dùng nhóm hoán vị để đếm các cấu hình "khác nhau sai khác một phép đối xứng" như số cách tô màu các đỉnh của một hình vuông.

Cách học hiệu quả

Tổ hợp học chủ yếu qua giải bài. Với mỗi công thức đếm, hãy kiểm tra bằng một chương trình nhỏ liệt kê mọi trường hợp với n nhỏ; với hàm sinh, dùng SymPy để khai triển chuỗi và đối chiếu hệ số. Với đồ thị, vẽ ví dụ và phản ví dụ nhỏ trước khi chứng minh, và tự cài đặt các thuật toán (Kruskal, Dijkstra, Ford–Fulkerson) — cài đặt buộc bạn hiểu đúng từng bước. Bài giảng và tài liệu về đường đi ngắn nhất, cây khung nhỏ nhất trong khóa Cấu trúc dữ liệu & Giải thuật trên OpenER là phần bổ trợ tốt cho bước thuật toán đồ thị.

Sau môn này

Bạn có nền tảng cho tối ưu tổ hợp và quy hoạch tuyến tính, thiết kế và phân tích thuật toán nâng cao, lý thuyết mã hóa, khoa học mạng, và các cuộc thi toán, tin học.

Giáo trình & sách tham khảo

Xem tất cả trong tab Sách

Giáo trình chính

Applied Combinatorics

Mitchel T. Keller, William T. Trotter · 2017 · Bản năm 2017

CC BY-SATrung bìnhTiếng Anh392 trang

Vì sao chọn: Giáo trình mở (CC BY-SA 4.0) của Georgia Tech, miễn phí trên trang của sách và được Viện Toán học Hoa Kỳ (AIM) chấp thuận. Bao trùm cả tổ hợp đếm lẫn đồ thị, thuật toán và luồng trên mạng với văn phong dễ đọc; các bước của lộ trình đi theo các chương này.

Nên đọc: Chương 2–5, Chương 7–9, Chương 11–15

Graph Theory

Reinhard Diestel · 2025 · Bản thứ 6

Có phíNâng caoTiếng Anh

Giáo trình lý thuyết đồ thị chuẩn mực bậc cao học (Springer, Graduate Texts in Mathematics 173); tác giả cho đọc miễn phí bản điện tử trên trang của sách. Dành cho người muốn đi sâu vào ghép cặp, liên thông, đồ thị phẳng, tô màu và lý thuyết Ramsey sau khi học xong lộ trình.

Các bước học

Đăng nhập để đánh dấu các bước đã hoàn thành.

  1. Bước 1: Xâu, tập hợp, hệ số nhị thức và quy nạp

    khoảng 6 giờ

    Xâu ký tự, hoán vị, tổ hợp, chứng minh tổ hợp, định lý nhị thức, hệ số đa thức; quy nạp, định nghĩa đệ quy và giải bài toán tổ hợp bằng đệ quy. Luyện tập: chứng minh ba đẳng thức về hệ số nhị thức bằng lập luận tổ hợp và kiểm tra lại bằng chương trình với n ≤ 10.

    • Đọc: Chương 2 Strings, Sets, and Binomial Coefficients; Chương 3 Induction — Applied Combinatorics
  2. Bước 2: Nguyên lý Dirichlet và bao hàm – loại trừ

    khoảng 6 giờ

    Nguyên lý chuồng bồ câu (Dirichlet) và các ứng dụng; công thức bao hàm – loại trừ, đếm toàn ánh, hoán vị lệch, hàm phi Euler. Luyện tập: đếm số toàn ánh từ tập 6 phần tử lên tập 3 phần tử bằng công thức rồi bằng chương trình; chứng minh trong 5 điểm bất kỳ trong hình vuông cạnh 2 luôn có hai điểm cách nhau không quá √2.

    • Đọc: Chương 4 Combinatorial Basics (4.1 The Pigeon Hole Principle); Chương 7 Inclusion-Exclusion — Applied Combinatorics
  3. Bước 3: Hàm sinh và hệ thức truy hồi

    khoảng 9 giờ

    Hàm sinh thường, định lý nhị thức Newton tổng quát, phân hoạch số nguyên, hàm sinh mũ; hệ thức truy hồi tuyến tính, phương pháp toán tử tiến, nghiệm bội, giải hệ thức truy hồi bằng hàm sinh và một ví dụ giải hệ thức truy hồi phi tuyến. Luyện tập: dùng hàm sinh đếm số cách đổi 100 nghìn đồng bằng các mệnh giá cho trước và kiểm tra hệ số bằng SymPy; giải hệ thức aₙ = 5aₙ₋₁ − 6aₙ₋₂ + 2ⁿ theo hai cách.

  4. Bước 4: Đồ thị: Euler, Hamilton, tô màu, đồ thị phẳng và cây

    khoảng 8 giờ

    Thuật ngữ cơ bản, đa đồ thị, đồ thị Euler và Hamilton, tô màu đồ thị, đồ thị hai phía, sắc số và clique, đồ thị phẳng, đếm cây có gán nhãn, liên hệ với độ phức tạp tính toán. Luyện tập: chứng minh đồ thị K₅ và K₃,₃ không phẳng bằng công thức Euler; cài đặt thuật toán tô màu tham lam và tìm một đồ thị mà nó dùng nhiều màu hơn sắc số.

  5. Bước 5: Thuật toán đồ thị, luồng trên mạng và ghép cặp

    khoảng 9 giờ

    Cây khung nhỏ nhất (Kruskal, Prim), đồ thị có hướng, thuật toán Dijkstra và chứng minh tính đúng; mạng, luồng và lát cắt, đường tăng luồng, thuật toán gán nhãn Ford–Fulkerson, định lý luồng cực đại – lát cắt cực tiểu; ghép cặp trên đồ thị hai phía và phân hoạch thành xích. Luyện tập: cài đặt Kruskal, Dijkstra và Ford–Fulkerson bằng Python, rồi quy bài toán phân công 5 người cho 5 việc về luồng cực đại. Khóa học, tài liệu và video trên trang giúp ôn phần cài đặt thuật toán.

    • Đọc: Chương 12 Graph Algorithms; Chương 13 Network Flows; Chương 14 Combinatorial Applications of Network Flows — Applied Combinatorics
  6. Bước 6: Lý thuyết Ramsey, phương pháp xác suất và định lý Pólya

    khoảng 4 giờ

    Số Ramsey nhỏ và cách ước lượng, định lý Ramsey, phương pháp xác suất; nhóm hoán vị, bổ đề Burnside và định lý đếm Pólya. Luyện tập: chứng minh R(3, 3) = 6; dùng bổ đề Burnside đếm số cách tô hai màu các đỉnh của hình vuông sai khác phép quay và phép lật, rồi kiểm tra bằng chương trình liệt kê.

    • Đọc: Chương 11 Applying Probability to Combinatorics; Chương 15 Pólya’s Enumeration Theorem — Applied Combinatorics

Khái niệm chính

Hệ số đa thức
Số cách chia n vật thành các nhóm có kích thước k₁, …, kₘ là n!/(k₁!⋯kₘ!); tổng quát hóa hệ số nhị thức.
Nguyên lý bao hàm – loại trừ
Đếm hợp của nhiều tập bằng cách cộng, trừ xen kẽ kích thước các giao; dùng để đếm toàn ánh và hoán vị lệch.
Hoán vị lệch (derangement)
Hoán vị không giữ phần tử nào ở vị trí cũ; số hoán vị lệch của n phần tử xấp xỉ n!/e.
Hàm sinh
Chuỗi lũy thừa hình thức ∑ aₙxⁿ mã hóa dãy (aₙ); phép toán trên dãy trở thành phép toán đại số trên chuỗi, giúp giải bài toán đếm và hệ thức truy hồi.
Hàm sinh mũ
Chuỗi ∑ aₙxⁿ/n!, thích hợp cho bài toán đếm có thứ tự như đếm xâu với ràng buộc về số lần xuất hiện của mỗi ký tự.
Phân hoạch số nguyên
Cách viết n thành tổng các số nguyên dương không kể thứ tự; hàm sinh của số phân hoạch là tích vô hạn ∏ 1/(1 − xᵏ).
Hệ thức truy hồi tuyến tính hệ số hằng
Hệ thức aₙ = c₁aₙ₋₁ + … + cₖaₙ₋ₖ (+ f(n)); nghiệm tổng quát xây từ nghiệm của phương trình đặc trưng, có xử lý nghiệm bội.
Đồ thị Hamilton
Đồ thị có chu trình đi qua mỗi đỉnh đúng một lần; khác với đồ thị Euler, chưa có tiêu chuẩn đơn giản nào để nhận biết.
Sắc số và clique
Sắc số χ(G) là số màu tối thiểu để tô đỉnh; clique là tập đỉnh đôi một kề nhau, nên χ(G) không nhỏ hơn kích thước clique lớn nhất.
Cây khung nhỏ nhất
Cây khung có tổng trọng số nhỏ nhất của đồ thị liên thông có trọng số; tìm bằng các thuật toán tham lam Kruskal hoặc Prim.
Luồng cực đại – lát cắt cực tiểu
Trong mạng có sức chứa, giá trị luồng lớn nhất từ nguồn tới đích bằng sức chứa nhỏ nhất của một lát cắt tách nguồn khỏi đích.
Ghép cặp trên đồ thị hai phía
Tập cạnh không chung đỉnh; cặp ghép có nhiều cạnh nhất tìm được bằng luồng, và định lý Hall cho điều kiện có ghép cặp phủ một phía.
Lý thuyết Ramsey
Mọi cấu trúc đủ lớn đều chứa một cấu trúc con có trật tự; ví dụ R(3, 3) = 6: mọi cách tô hai màu các cạnh của đồ thị đầy đủ 6 đỉnh đều có tam giác cùng màu.
Định lý đếm Pólya
Đếm số cấu hình khác nhau sai khác một phép đối xứng bằng cách lấy trung bình số điểm bất động trên nhóm hoán vị (bổ đề Burnside) và mở rộng thành đa thức chỉ số chu trình.

Học xong để làm gì

  • Thiết kế thuật toán: phân tích độ phức tạp bằng hệ thức truy hồi, thuật toán đồ thị trong định tuyến và bản đồ số
  • Vận trù học và logistics: luồng trên mạng cho bài toán vận tải, phân công và lập lịch
  • Mạng máy tính và khoa học mạng: độ tin cậy mạng, lát cắt cực tiểu, phân tích mạng xã hội
  • Lý thuyết mã hóa và mật mã học: thiết kế tổ hợp và đếm cấu hình trong mã sửa lỗi
  • Hóa học và sinh học: đếm đồng phân phân tử bằng định lý Pólya, mạng tương tác protein
  • Xếp lịch thi, phân phòng, phân bổ tần số vô tuyến bằng tô màu đồ thị

Câu hỏi thường gặp

Môn này khác gì Toán rời rạc?

Toán rời rạc giới thiệu các khái niệm và công cụ cơ bản. Môn này đi sâu: hàm sinh và hệ thức truy hồi tổng quát, nguyên lý bao hàm – loại trừ nâng cao, thuật toán đồ thị, luồng trên mạng, lý thuyết Ramsey và định lý Pólya — với nhiều chứng minh hơn.

Có cần biết lập trình không?

Không bắt buộc, nhưng rất nên. Viết chương trình liệt kê để kiểm tra công thức đếm và tự cài đặt các thuật toán đồ thị là cách học hiệu quả nhất; Python là đủ.

Phần định lý Pólya cần nhóm hoán vị, tôi chưa học đại số trừu tượng thì sao?

Giáo trình chính tự giới thiệu phần nhóm hoán vị cần thiết ngay trong chương đó. Đây là bước ngắn cuối lộ trình, mang tính mở rộng; bạn có thể quay lại sau khi học đại số trừu tượng.

Nên đọc thêm sách nào để đi sâu lý thuyết đồ thị?

Graph Theory của Diestel là giáo trình chuẩn bậc cao học, tác giả cho đọc miễn phí bản điện tử trên trang của sách. Nếu muốn một cuốn nhẹ nhàng về đếm và đồ thị với nhiều lời giải, hãy chọn A Walk Through Combinatorics của Bóna.

Môn này có giúp ích cho thi lập trình hay thi olympic toán không?

Có, rất nhiều. Đếm, hàm sinh, nguyên lý Dirichlet, đồ thị và luồng là các chủ đề xuất hiện thường xuyên trong thi olympic toán sinh viên và thi lập trình thuật toán.

Chọn nguồn tự học

Học qua giải bài: chọn nguồn có bài tập nhiều mức độ và tự kiểm tra công thức đếm bằng chương trình nhỏ liệt kê các trường hợp.