Tô màu đồ thị trong đời sống: xếp lịch thi, chia ca, xếp chỗ ngồi

Tô màu đồ thị là cách giải những bài toán "không được trùng": xếp lịch thi sao cho không học sinh nào thi hai môn cùng giờ, chia ca sao cho hai người không hợp không chung ca, xếp chỗ ngồi để hai bạn hay nói chuyện không ngồi cạnh. Mỗi việc là một đỉnh, mỗi cặp xung đột là một cạnh, mỗi khung giờ hay ca là một "màu". Số màu ít nhất cần dùng cho biết cần ít nhất bao nhiêu buổi thi, bao nhiêu ca.

Từ bản đồ đến lịch thi

Bài toán bốn màu hỏi cách tô bản đồ để hai nước kề nhau khác màu. Các vùng đất có thể thay bằng bất cứ thứ gì: môn thi, cuộc họp, đài phát thanh. "Kề nhau" thay bằng "xung đột". Đó là bài toán tô màu đồ thị:

• Đỉnh: các việc cần xếp (môn thi, cuộc họp, người).
• Cạnh: nối hai việc không được xếp cùng lúc.
• Màu: khung giờ, phòng, ca làm, tần số.
• Yêu cầu: hai đỉnh nối nhau phải khác màu.

Số màu ít nhất cần dùng gọi là sắc số của đồ thị. Với bản đồ trên mặt phẳng, sắc số không quá 4. Với lịch thi, có thể cần nhiều hơn nhiều.

Ví dụ: xếp lịch thi cuối kỳ

Một trường có sáu môn thi: Toán, Văn, Anh, Lý, Hoá, Sử. Vì học sinh chọn môn khác nhau, có những cặp môn có chung học sinh, không được thi cùng buổi: Toán–Lý, Toán–Hoá, Lý–Hoá, Văn–Sử, Anh–Toán, Anh–Văn.

Toán, Lý, Hoá đôi một xung đột (ba môn tạo thành tam giác) → cần ít nhất 3 buổi. Thử xếp:

• Buổi 1: Toán, Văn
• Buổi 2: Lý, Anh, Sử
• Buổi 3: Hoá

Kiểm: Toán–Văn không xung đột; Lý, Anh, Sử đôi một không xung đột. Ba buổi là đủ và không thể ít hơn.

Cách tô màu nhanh: thuật toán tham lam

Với bài lớn hàng trăm môn, người ta dùng cách tham lam đơn giản:

1. Xếp các đỉnh theo thứ tự số xung đột giảm dần (đỉnh "khó" trước).
2. Lần lượt từng đỉnh, gán màu có số nhỏ nhất mà chưa láng giềng nào dùng.

Cách này không phải lúc nào cũng ra số màu ít nhất, nhưng thường khá tốt, và chạy rất nhanh. Tìm số màu ít nhất chính xác cho đồ thị lớn là bài toán khó — cùng họ với bài toán người du lịch.

Một mẹo: thứ tự xét đỉnh ảnh hưởng nhiều đến kết quả. Xét đỉnh nhiều xung đột trước gần như luôn tốt hơn xét ngẫu nhiên. Nhà toán học Daniel Brélaz đề xuất năm 1979 một cải tiến: mỗi bước chọn đỉnh đang bị "ép" nhiều nhất (láng giềng đã dùng nhiều màu khác nhau nhất).

Những bài toán đời thường là tô màu đồ thị

Ô chữ số Sudoku cũng là một bài tô màu: 81 ô là đỉnh, hai ô cùng hàng, cột hoặc khối nối nhau, chín chữ số là chín màu.

Đèn giao thông: một ví dụ hay

Ở một ngã tư, mỗi luồng xe (đi thẳng hướng bắc, rẽ trái từ hướng đông…) là một đỉnh. Hai luồng cắt nhau thì nối cạnh. Mỗi pha đèn xanh là một màu. Số màu ít nhất là số pha đèn ít nhất để mọi luồng đều được đi mà không va nhau. Kỹ sư giao thông còn tính thêm thời gian mỗi pha, người đi bộ, giờ cao điểm — nhưng khung xương của bài toán chính là tô màu đồ thị.

Khi số màu bị giới hạn

Thực tế thường ngược lại: trường chỉ có 4 buổi thi, công ty chỉ có 3 ca. Câu hỏi thành "có tô được bằng k màu không?" Nếu không, phải nới điều kiện: cho vài học sinh thi bù, chấp nhận một cặp xung đột nhẹ. Đây là lúc các phần mềm xếp lịch dùng thêm "điểm phạt" cho mỗi xung đột nhẹ và tìm lịch có tổng điểm phạt nhỏ nhất.

Góc nhìn hôm nay: xếp lịch trực nhật bằng tô màu

Lớp có mười hai bạn, cần chia nhóm trực nhật cho năm ngày trong tuần. Có vài cặp không nên chung nhóm (hay cãi nhau, hoặc nhà xa nhau không về cùng được). Vẽ mười hai chấm, nối các cặp không nên chung. Tô màu bằng năm màu — mỗi màu là một ngày. Nếu cần nhiều hơn năm màu, đó là tín hiệu danh sách "không nên chung" quá chặt. Bài tập nhỏ này giúp học sinh thấy toán học không chỉ là tính số, mà là cách sắp xếp đời sống cho gọn.