Tô màu đồ thị xong, vì sao vẫn thiếu phòng?

1. Biểu diễn xung đột thành đồ thị

Mỗi lớp học phần là một đỉnh. Hai lớp có chung nhóm sinh viên hoặc chung giảng viên thì nối cạnh, vì chúng cần học ở hai ca khác nhau. Một màu tương ứng một ca. Nếu hai đỉnh kề nhau luôn có màu khác nhau, phép tô màu đã xử lý phần chống trùng được biểu diễn bằng cạnh. Đồ thị cho ta một hình ảnh ngắn gọn về các cặp không thể học đồng thời.

Xét ba lớp A, B, C. C xung đột với A và B. A và B không có cạnh vì khác giảng viên và khác nhóm sinh viên. Với hai ca, một phép tô màu hợp lệ là A, B học ca 1 và C học ca 2. Hãy dừng ở đây và dự đoán liệu lịch đã đủ điều kiện để công bố. Câu trả lời phụ thuộc vào tập phòng mỗi lớp được phép sử dụng.

2. Dựng phản ví dụ từ một nút thắt tài nguyên

Cả A và B là lớp thực hành và chỉ dùng được Lab. C là lớp lý thuyết, dùng P101. Trong ca 1 có hai lớp và tổng cộng hai phòng, nhưng cả hai lớp chỉ có một phòng tương thích. Chúng không thể cùng học ở ca 1. Nếu chỉ nhìn số lớp và số phòng, ta sẽ kết luận nhầm rằng tài nguyên vừa đủ. Điều cần kiểm tra là số phòng tương thích với từng nhóm lớp.

Với một ca cố định, tạo đồ thị hai phía. Bên trái là các lớp trong ca. Bên phải là các phòng có thể dùng. Nối lớp với phòng khi phòng đáp ứng loại, sức chứa và thiết bị. Ta cần một ghép cặp phủ mọi lớp. Trong phản ví dụ, nhóm {A,B} chỉ có tập phòng lân cận {Lab}. Số phòng lân cận nhỏ hơn số lớp, nên ghép đầy đủ là bất khả thi. Đây là trường hợp trực quan của điều kiện Hall.

3. Tô màu xong, kiểm tra ghép phòng bằng đường tăng

"""Kiểm tra một lịch hai ca, sau đó tìm phương án ghép phòng."""
from collections import defaultdict


def trung_nhom(cac_canh, ca):
    return [(a, b) for a, b in cac_canh if ca[a] == ca[b]]


def ghep_phong(mien_phong):
    """Trả ánh xạ lớp -> phòng, hoặc None nếu không có ghép đầy đủ."""
    chu_phong = {}

    def gan(lop, da_xet):
        for phong in sorted(mien_phong[lop]):
            if phong in da_xet:
                continue
            da_xet.add(phong)
            truoc = chu_phong.get(phong)
            if truoc is None or gan(truoc, da_xet):
                chu_phong[phong] = lop
                return True
        return False

    for lop in sorted(mien_phong, key=lambda key: (len(mien_phong[key]), key)):
        if not gan(lop, set()):
            return None
    return {lop: phong for phong, lop in chu_phong.items()}


def kiem_lich(canh, ca, mien_phong):
    if trung_nhom(canh, ca):
        return None
    theo_ca = defaultdict(dict)
    for lop, tiet in ca.items():
        theo_ca[tiet][lop] = mien_phong[lop]
    result = {}
    for tiet, mien in sorted(theo_ca.items()):
        assignment = ghep_phong(mien)
        if assignment is None:
            return None
        result[tiet] = assignment
    return result


if __name__ == "__main__":
    canh = [("A", "C"), ("B", "C")]
    rooms = {"A": {"Lab"}, "B": {"Lab"}, "C": {"P101"}}
    schedule = {"A": 1, "B": 1, "C": 2}
    assert trung_nhom(canh, schedule) == []
    assert kiem_lich(canh, schedule, rooms) is None
    rooms["B"].add("Lab2")
    assert kiem_lich(canh, schedule, rooms) == {
        1: {"A": "Lab", "B": "Lab2"}, 2: {"C": "P101"}
    }
    assert ghep_phong({"A": {"R1","R2"}, "B": {"R1","R3"}, "C": {"R1","R3"}})
    print("Màu hợp lệ. Ghép phòng sau khi thêm Lab2:", kiem_lich(canh, schedule, rooms))

Chạy python to_mau_va_ghep_phong.py. Hàm trung_nhom kiểm tra các cạnh. Hàm ghep_phong thử thêm từng lớp vào ghép hiện tại. Nếu một phòng đã có chủ, chương trình thử chuyển chủ cũ sang một phòng khác rồi mới gán phòng vừa giải phóng. Tập phòng đã xét ngăn việc lặp lại cùng một phòng trong một lần tìm đường tăng. Khi không thể tăng kích thước ghép, có ít nhất một lớp không có phòng trong ca đó.

Thêm Lab2 chỉ tương thích với B. Lúc này A nhận Lab, B nhận Lab2 và C nhận P101. Phép tô màu trước đó trở thành lịch có phòng. Nếu không có Lab2, cần thay ca, thêm phòng tương thích hoặc đổi một điều kiện nghiệp vụ đã được duyệt. Việc gán P101 cho B sẽ tạo ra một lịch trên giấy, nhưng lớp thực hành không có môi trường cần thiết để học.

4. Khi nào nên dùng cách phân rã theo ca?

Ghép phòng theo từng ca hợp lý khi các ca không giao nhau và quyết định phòng trong một ca không ảnh hưởng ca khác. Với bài toán nhiều cơ sở, giảng viên có thể cần đủ thời gian di chuyển giữa hai ca liên tiếp. Khi một lựa chọn phòng làm thay đổi cơ sở, việc ghép riêng từng ca có thể bỏ sót xung đột liên ca. Tương tự, yêu cầu giữ cùng phòng cho một lớp trong nhiều buổi tạo liên kết giữa các quyết định.

Bài tập. Trong ca 1, cho A dùng {Lab1,Lab2}, B dùng {Lab1} và D dùng {Lab2,Lab3}. Tìm một cách gán bằng tay. Sau đó bỏ Lab3. Hãy tìm một nhóm lớp có tập phòng tương thích quá nhỏ và diễn giải vì sao thêm một phòng lý thuyết không giải quyết được vấn đề. Có thể thử trường hợp phòng chuyên dụng trong mô phỏng xếp lịch.

Đọc thêm về điều kiện tồn tại ghép cặp tại MIT · Matching and Hall’s Theorem.