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.
| Môn | Xung đột với | Số xung đột |
|---|---|---|
| Toán | Lý, Hoá, Anh | 3 |
| Lý | Toán, Hoá | 2 |
| Hoá | Toán, Lý | 2 |
| Anh | Toán, Văn | 2 |
| Văn | Sử, Anh | 2 |
| Sử | Văn | 1 |
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:
- Xếp các đỉnh theo thứ tự số xung đột giảm dần (đỉnh "khó" trước).
- 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ị
| Bài toán | Đỉnh | Cạnh (xung đột) | Màu |
|---|---|---|---|
| Lịch thi | Môn thi | Có chung thí sinh | Buổi thi |
| Xếp phòng họp | Cuộc họp | Trùng giờ | Phòng |
| Chia ca | Nhân viên | Không thể làm cùng ca | Ca |
| Tần số phát sóng | Trạm phát | Gần nhau, gây nhiễu | Tần số |
| Xếp chỗ ngồi | Học sinh | Không nên ngồi cạnh | Bàn / nhóm |
| Đèn giao thông | Luồng xe | Cắt nhau ở ngã tư | Pha đèn |
| Bố trí chuồng thú, bể cá | Loài | Không nuôi chung được | Chuồng, bể |
Ô 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.
Câu hỏi thường gặp
Tô màu đồ thị là gì?
Là gán màu cho các đỉnh của đồ thị sao cho hai đỉnh nối nhau bằng một cạnh luôn khác màu. Số màu ít nhất cần dùng gọi là sắc số của đồ thị.
Tô màu đồ thị dùng để xếp lịch thi thế nào?
Mỗi môn thi là một đỉnh, hai môn có chung thí sinh thì nối cạnh, mỗi buổi thi là một màu. Tô màu sao cho hai môn nối nhau khác màu, số màu ít nhất là số buổi thi ít nhất cần có.
Sắc số là gì?
Là số màu ít nhất cần để tô các đỉnh của một đồ thị mà không có hai đỉnh kề nhau cùng màu. Ví dụ ba đỉnh đôi một nối nhau có sắc số là 3.
Có cách nào tìm nhanh số màu ít nhất không?
Với đồ thị lớn, tìm chính xác số màu ít nhất là bài toán khó. Người ta thường dùng thuật toán tham lam: xét đỉnh nhiều xung đột trước và gán màu nhỏ nhất còn dùng được.
Sudoku có liên quan đến tô màu đồ thị không?
Có. Mỗi ô là một đỉnh, hai ô cùng hàng, cột hoặc khối được nối cạnh, chín chữ số là chín màu. Giải Sudoku là hoàn thành một cách tô màu đồ thị đã tô sẵn một phần.