Bài 9: Xếp lịch thi sao cho không ai bị trùng giờ? Bài toán tô màu đồ thị trong đời sống

Một trường có 7 môn thi học kỳ. Nhiều học sinh học cả Toán lẫn Lý, nên hai môn đó không được thi cùng ca. Cần ít nhất bao nhiêu ca thi? Câu hỏi đời thường này chính là bài toán tô màu đồ thị – và nó khó hơn bạn tưởng rất nhiều.

Bài thứ chín của chuyên mục "Thuật toán trong đời sống". Bài này cho thấy vì sao "tham lam" dễ cài nhưng không phải lúc nào cũng tối ưu, và vì sao một số bài toán đến nay vẫn chưa có thuật toán nhanh.

1. Từ lịch thi đến đồ thị

Biểu diễn mỗi môn là một đỉnh. Hai môn có chung học sinh thì nối bằng một cạnh – nghĩa là không được thi cùng ca. Mỗi ca thi là một màu. Yêu cầu: tô màu các đỉnh sao cho hai đỉnh kề nhau khác màu, dùng ít màu nhất. Số màu ít nhất đó gọi là sắc số của đồ thị.

Hình trên là đồ thị xung đột của 7 môn, tô bằng 3 màu = 3 ca thi: Toán, Hóa · Văn, Tin · Anh, Lý, Sinh. Không thể dùng 2 màu vì đồ thị có tam giác Toán – Văn – Anh (ba môn đôi một xung đột).

2. Thuật toán tham lam Welsh–Powell

Năm 1967, D. J. A. Welsh và M. B. Powell công bố bài báo có tên rất "đời": "Một cận trên cho sắc số của đồ thị và ứng dụng vào bài toán xếp thời khóa biểu". Thuật toán:

1. Sắp xếp các đỉnh theo bậc giảm dần (môn xung đột với nhiều môn nhất xếp trước).
2. Lần lượt gán cho mỗi đỉnh màu nhỏ nhất chưa bị các đỉnh kề dùng.

Code C++ và Python

#include <bits/stdc++.h>
using namespace std;
// Xếp lịch thi: mỗi môn là một đỉnh, hai môn có chung học sinh thì nối cạnh (không được thi cùng ca)
int main(){
    vector<string> mon = {"Toan", "Van", "Anh", "Ly", "Hoa", "Sinh", "Tin"};
    vector<pair<int,int>> xungDot = {{0,1},{0,2},{0,3},{0,6},{1,2},{1,5},{2,4},{3,4},{3,6},{4,5},{5,6}};
    int n = mon.size();
    vector<vector<int>> g(n);
    for(auto [u, v] : xungDot){ g[u].push_back(v); g[v].push_back(u); }
    // Welsh–Powell: xét các đỉnh theo bậc giảm dần, gán màu (ca thi) nhỏ nhất chưa bị hàng xóm dùng
    vector<int> order(n); iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b){ return g[a].size() > g[b].size(); });
    vector<int> ca(n, -1);
    for(int u : order){
        set<int> used; for(int v : g[u]) if(ca[v] >= 0) used.insert(ca[v]);
        int c = 0; while(used.count(c)) c++;
        ca[u] = c;
    }
    int soCa = *max_element(ca.begin(), ca.end()) + 1;
    for(int c = 0; c < soCa; c++){
        cout << "Ca " << c + 1 << ":";
        for(int u = 0; u < n; u++) if(ca[u] == c) cout << " " << mon[u];
        cout << "\n";
    }
}

mon = ["Toan", "Van", "Anh", "Ly", "Hoa", "Sinh", "Tin"]
xung_dot = [(0,1),(0,2),(0,3),(0,6),(1,2),(1,5),(2,4),(3,4),(3,6),(4,5),(5,6)]
g = {u: set() for u in range(len(mon))}
for u, v in xung_dot:
    g[u].add(v); g[v].add(u)

# Welsh–Powell: đỉnh bậc cao xếp trước, chọn ca nhỏ nhất không trùng với môn xung đột
ca = {}
for u in sorted(g, key=lambda x: -len(g[x])):
    used = {ca[v] for v in g[u] if v in ca}
    c = 0
    while c in used: c += 1
    ca[u] = c

for c in range(max(ca.values()) + 1):
    print(f"Ca {c + 1}:", ", ".join(mon[u] for u in g if ca[u] == c))

Kết quả chạy code:

Ca	Môn thi (tham lam)
1	Toán, Hóa
2	Văn, Lý
3	Anh, Sinh
4	Tin

Tham lam dùng 4 ca, trong khi tối ưu chỉ cần 3 ca! Đặt Lý cùng ca với Văn khiến môn Tin – xung đột với Toán, Lý, Sinh – không còn chỗ trong 3 ca đầu. Thuật toán tham lam cho lời giải nhanh và thường khá tốt, nhưng không đảm bảo tối ưu.

3. Vì sao bài toán này khó?

• Năm 1972, Richard Karp công bố danh sách 21 bài toán NP-đầy đủ nổi tiếng, trong đó có bài toán sắc số. Nghĩa là nếu ai tìm ra thuật toán thời gian đa thức cho tô màu đồ thị, người đó cũng giải được hàng nghìn bài toán khó khác – và nhận giải thưởng 1 triệu USD của Viện Clay về bài toán P vs NP.
• Ngay cả câu hỏi "tô được bằng 3 màu không?" cũng đã là NP-đầy đủ. Với đồ thị nhỏ như ví dụ trên, ta có thể thử hết 3⁷ = 2.187 cách; với 100 môn thì có 3¹⁰⁰ ≈ 5 × 10⁴⁷ cách – dù thử một tỷ cách mỗi giây cũng mất hơn 10³¹ năm.

Định lý bốn màu: chứng minh nhờ máy tính

Mọi bản đồ trên mặt phẳng đều tô được bằng 4 màu sao cho hai nước chung biên giới khác màu. Năm 1976, Kenneth Appel và Wolfgang Haken (Đại học Illinois) công bố chứng minh – định lý toán học lớn đầu tiên được chứng minh với sự trợ giúp của máy tính, dựa một phần vào khoảng 1.200 giờ tính toán.

4. Tô màu đồ thị ở đâu trong đời sống?

• Xếp lịch thi, thời khóa biểu: đúng như tên bài báo của Welsh và Powell.
• Trình biên dịch: khi dịch code C++, máy cần quyết định biến nào nằm trong thanh ghi CPU nào. Năm 1982, Gregory Chaitin (IBM) trình bày cách giải bằng tô màu đồ thị: hai biến "sống" cùng lúc thì không chung thanh ghi. Mỗi lần bạn bấm biên dịch, thuật toán này đang chạy.
• Phân tần số sóng: hai trạm phát gần nhau phải dùng tần số khác nhau để không nhiễu.
• Lịch thi đấu thể thao: theo Amazon, giải bóng bầu dục NFL có "hơn một triệu tỷ" phương án lịch mỗi mùa (32 đội, 272 trận, 576 khung giờ). Họ dùng hàng nghìn máy chủ đám mây để phân tích hơn 80.000 lịch hợp lệ trước khi chọn.

5. Bạn học được gì từ đây?

• Mô hình hóa là kỹ năng quan trọng nhất: nhìn ra lịch thi là đồ thị thì mới áp dụng được thuật toán.
• Đồ thị hai phía (tô được bằng 2 màu) kiểm tra được bằng BFS/DFS trong O(n + m) – nhưng từ 3 màu trở lên thì bài toán trở nên NP-khó.
• Thực tế thường dùng tham lam + tìm kiếm cục bộ để có lịch "đủ tốt".

Bài tập luyện tập

• CSES – Building Teams (kiểm tra đồ thị tô được bằng 2 màu)
• Codeforces 862B – Mahmoud and Ehab and the bipartiteness

Thử thách: hãy sửa code để thử tất cả các thứ tự duyệt đỉnh. Có thứ tự nào giúp thuật toán tham lam tìm ra lịch 3 ca không? Chia sẻ trong phần bình luận nhé!

📖 ĐỌC TIẾP: THUẬT TOÁN TRONG ĐỜI SỐNG

Bài 10: Máy tính giải Sudoku trong tích tắc thế nào? Thuật toán quay lui và cắt nhánh

Đọc tiếp: Sudoku & quay lui →

← Bài trước: file ZIP & mã HuffmanXem tất cả 27 bài →

Nguồn tham khảo

• Welsh & Powell (1967) – An upper bound for the chromatic number of a graph and its application to timetabling problems
• GraphStream – Welsh-Powell algorithm
• Wikipedia – Karp's 21 NP-complete problems
• Đại học Illinois – Kenneth Appel và định lý bốn màu
• IBM Research – Chaitin (1982), Register allocation & spilling via graph coloring
• Amazon – The NFL teams up with AWS to create 2021 schedule
• Clay Mathematics Institute – P vs NP