Tô màu cạnh (Kőnig và Vizing)
Tô màu cạnh sao cho hai cạnh chung đỉnh khác màu: đồ thị hai phía cần đúng Δ màu (định lý Kőnig, lật đường xen kẽ), đồ thị đơn cần Δ hoặc Δ + 1 màu (định lý Vizing, quạt và đường xen kẽ), cả hai trong O(nm).
Tô màu cạnh (edge coloring) là gán cho mỗi cạnh của đồ thị một màu sao cho hai cạnh chung một đỉnh luôn khác màu. Số màu ít nhất cần dùng gọi là sắc số cạnh (chromatic index), ký hiệu . Gọi là bậc lớn nhất của đồ thị: hiển nhiên , vì cạnh tại đỉnh bậc lớn nhất phải đôi một khác màu. Trang này trình bày hai kết quả kinh điển kèm thuật toán xây dựng: định lý Kőnig (đồ thị hai phía tô được bằng đúng màu) và định lý Vizing (đồ thị đơn bất kỳ tô được bằng màu). Cả hai đều cài được trong , trong khi thử mọi cách tô là hàm mũ.
Mỗi lớp màu là một cặp ghép (matching): tập cạnh không chung đỉnh. Vì vậy tô màu cạnh bằng màu chính là chia tập cạnh thành cặp ghép. Đó là lý do bài toán xuất hiện khi xếp lịch: mỗi "ngày" (hay "lượt", "ca") là một cặp ghép, mỗi người chỉ tham gia nhiều nhất một trận mỗi ngày.
Ý tưởng / Trực giác
Tô từng cạnh và "màu rảnh"
Cả hai thuật toán đều tô lần lượt từng cạnh, giữ bất biến: các cạnh đã tô luôn là một cách tô hợp lệ. Với một đỉnh , màu gọi là rảnh tại (free) nếu không cạnh nào đã tô tại mang màu .
Khi thêm cạnh chưa tô: đang có tối đa cạnh đã tô, nên với bảng màu luôn còn ít nhất một màu rảnh tại , tương tự tại . Nếu có một màu rảnh tại cả hai đầu, tô luôn. Khó khăn là khi màu rảnh tại đang bận tại và ngược lại. Công cụ chung để gỡ là đường xen kẽ.
Đường xen kẽ hai màu (-path)
Lấy hai màu và chỉ nhìn các cạnh màu hoặc . Mỗi đỉnh có nhiều nhất một cạnh màu và một cạnh màu , nên đồ thị con này có bậc : nó gồm các đường đi và chu trình rời nhau, màu trên mỗi đường xen kẽ
Đổi màu cả một thành phần (mọi thành , mọi thành ) vẫn cho cách tô hợp lệ: đỉnh trong của đường vẫn có đúng một cạnh và một cạnh ; đỉnh đầu mút của đường chỉ có một trong hai màu nên đổi xong vẫn không trùng. Tác dụng duy nhất thấy được là tại hai đầu mút, màu rảnh bị đổi từ sang hoặc ngược lại. Đây là thao tác "lật" dùng trong mọi chứng minh dưới đây.
Định lý Kőnig: đồ thị hai phía cần đúng màu
Định lý (Kőnig, 1916). Với đồ thị hai phía (kể cả có cạnh bội), .
Chứng minh có tính xây dựng. Dùng bảng màu. Thêm cạnh với ở phía trái, ở phía phải. Chọn rảnh tại , rảnh tại .
- Nếu cũng rảnh tại : tô màu .
- Ngược lại, xét đường xen kẽ bắt đầu từ : đi theo cạnh màu ra khỏi , rồi cạnh màu , rồi ... ( không có cạnh nên là đầu mút). Đường này không bao giờ chạm . Thật vậy, cạnh thứ màu , cạnh thứ màu . Vì rảnh tại , nếu đường tới thì nó phải tới qua một cạnh màu , tức là sau một số chẵn cạnh. Nhưng và ở hai phía khác nhau, mọi đường từ tới đều có độ dài lẻ. Mâu thuẫn.
- Lật đường đó. Tại , cạnh màu thành màu (đúng màu đang rảnh tại ), nên trở thành rảnh tại . Tại không có gì thay đổi vì không nằm trên đường. Giờ rảnh ở cả hai đầu, tô màu .
Mỗi cạnh luôn tô được bằng một trong màu, nên ; kết hợp chặn dưới ta có đẳng thức.
Hệ quả. Đồ thị hai phía -chính quy (mọi đỉnh bậc ) tách được thành cặp ghép hoàn hảo rời nhau: mỗi lớp màu chạm mọi đỉnh, vì mỗi đỉnh có đủ cạnh với màu khác nhau.
Vì sao đồ thị tổng quát có thể cần
Tam giác có nhưng ba cạnh đôi một chung đỉnh, nên cần màu. Chứng minh Kőnig hỏng đúng ở chỗ dùng tính chẵn lẻ: trong chu trình lẻ, đường từ có thể quay về .
Các đồ thị đầy đủ: khi chẵn và khi lẻ. Với lẻ, mỗi lớp màu ghép được nhiều nhất cạnh, cần ít nhất màu. Đồ thị Petersen () cũng cần màu.
Định lý Vizing: hoặc
Định lý (Vizing, 1964). Với đồ thị đơn (không cạnh bội, không khuyên), .
Đồ thị có gọi là lớp 1, có gọi là lớp 2. Định lý gọn đến bất ngờ: chỉ có hai khả năng. Nhưng quyết định đồ thị thuộc lớp nào là NP-khó (Holyer, 1981), kể cả khi chỉ xét đồ thị -chính quy. Vì vậy trong thi đấu, khi đề yêu cầu "ít màu nhất", thường thì hoặc đồ thị có cấu trúc đặc biệt (hai phía, cây, đồ thị đầy đủ...), hoặc đề chỉ cần màu.
Thuật toán xây dựng (Misra và Gries). Dùng bảng màu. Bây giờ mỗi đỉnh luôn có ít nhất một màu rảnh, kể cả khi mọi cạnh tại đã tô (). Thêm cạnh :
- Dựng quạt (fan) quanh : dãy đỉnh là các hàng xóm phân biệt của sao cho với mọi , màu của cạnh rảnh tại . Cách dựng: lấy là một màu rảnh tại ; nếu có cạnh màu tới một đỉnh chưa trong quạt thì thêm vào quạt và lặp lại; nếu không thì dừng. Khi dừng, rảnh tại và hoặc rảnh tại , hoặc là màu của cạnh với một nào đó.
- Xoay quạt (rotate) là thao tác then chốt: nếu rảnh tại thì ta có thể tô bằng màu của , tô bằng màu của , ..., tô bằng màu của , bỏ màu rồi tô nó bằng . Mỗi bước hợp lệ vì màu của rảnh tại (định nghĩa quạt). Bước cuối cần rảnh tại cả và .
- Làm rảnh tại . Lấy là một màu rảnh tại . Lật đường xen kẽ bắt đầu từ (đường này bắt đầu bằng cạnh màu nếu có). Sau khi lật, rảnh tại .
- Chọn là đỉnh đầu tiên của quạt mà rảnh. Xoay quạt từ tới rồi tô màu .
Vì sao bước 4 luôn tìm được hợp lệ. Trường hợp rảnh tại từ đầu thì đường ở bước 3 rỗng, có rảnh. Trường hợp là màu của : theo định nghĩa quạt, rảnh tại , và cũng rảnh tại . Đường từ đi qua trước tiên và chỉ có một đầu mút còn lại, nên nó không thể kết thúc ở cả lẫn :
- Nếu đường không kết thúc ở : sau khi lật vẫn rảnh tại . Phần quạt không bị ảnh hưởng (màu các cạnh với không phải hay ), nên nằm trong đoạn này.
- Nếu đường kết thúc ở : nó tới qua một cạnh màu , lật xong cạnh đó thành nên rảnh tại . Mà cạnh giờ mang màu , nên toàn bộ quạt vẫn hợp lệ, và vẫn rảnh tại (đường không kết thúc ở đó).
Trong cả hai trường hợp, đoạn quạt từ tới hợp lệ và rảnh tại lẫn , nên bước xoay thành công. Cạnh nào cũng tô được bằng màu.
Ví dụ chạy tay
Kőnig: một lần lật đường
Đồ thị hai phía trái , phải , các cạnh theo thứ tự thêm vào: . Đỉnh có bậc nên , dùng màu . Mỗi bước chọn màu rảnh nhỏ nhất.
| Cạnh | Rảnh tại đầu trái | Rảnh tại đầu phải | Xử lý | Màu |
|---|---|---|---|---|
| trùng, tô luôn | ||||
| trùng, tô luôn | ||||
| trùng, tô luôn | ||||
| màu bận tại , lật đường từ | ||||
| màu rảnh tại , tô luôn | ||||
| màu rảnh tại , tô luôn |
Ở cạnh : màu rảnh tại nhưng đã có cạnh màu . Đường xen kẽ từ là (đỉnh không có cạnh màu nên dừng). Đường dài (lẻ) và kết thúc ở phía trái tại đỉnh , đúng như chứng minh. Lật đường: thành , thành , thành . Giờ màu rảnh tại , tô màu .
graph 3 1 1 2 1 1 2 2 2 3 1 3 name 1 1 name 2 2 name 3 3 name 4 a name 5 b name 6 c pos 1 0 0 pos 2 0 90 pos 3 0 180 pos 4 200 0 pos 5 200 90 pos 6 200 180 step Đã tô 3a, 1b màu 1 (đỏ) và 1a màu 2 (xanh lá). Cạnh 2b (cam) chưa tô highlight red 3-4 1-5 highlight green 1-4 highlight orange 2-5 step Đường xen kẽ 1/2 xuất phát từ b: b, 1, a, 3 path purple 5 1 4 3 step Lật đường: 1b và 3a thành màu 2, 1a thành màu 1. Màu 1 rảnh tại b, tô 2b màu 1 clear highlight green 1-5 3-4 highlight red 1-4 2-5 step Tô nốt 2c màu 2 và 1c màu 3 (xanh dương): mỗi đỉnh có các cạnh khác màu highlight green 2-6 highlight blue 1-6
Kết quả: , , , , , . Đỉnh có ba cạnh màu ; mọi đỉnh khác có các cạnh khác màu.
Vizing: quạt, lật đường và xoay
Đồ thị đơn đỉnh, , bảng màu . Năm cạnh đầu đã được tô; ta xem bước thêm cạnh cuối với , . Nhãn trên cạnh là màu hiện tại, ? là cạnh đang thêm.
graph 1 2 2 1 5 1 2 4 1 3 4 3 3 5 2 4 5 ? pos 1 0 0 pos 2 160 0 pos 5 0 150 pos 3 80 230 pos 4 160 150 step Trạng thái trước khi thêm (4, 5) highlight orange 4-5 step Quạt quanh u = 4: f0 = 5, f1 = 3, f2 = 2 highlight purple 4-3 4-2 label 5 f0 label 3 f1 label 2 f2
Bước 1: dựng quạt quanh (các cạnh tại : , , nên màu rảnh nhỏ nhất tại là ).
| Đỉnh quạt | Màu tại đỉnh | Màu rảnh | Cạnh của mang màu | Hành động |
|---|---|---|---|---|
| thêm | ||||
| thêm | ||||
| , nhưng đã trong quạt | dừng, |
Vậy là màu của , tức , và rảnh tại .
Bước 2: lật đường từ . Đường là , dừng ở vì không có cạnh màu . Đường kết thúc đúng ở (trường hợp thứ hai của chứng minh). Lật xong: , . Bây giờ rảnh tại .
Bước 3: tìm là đỉnh quạt đầu tiên có màu rảnh: vừa nhận màu (cạnh -), cũng có màu , có màu nên .
Bước 4: xoay quạt từ tới : nhận màu cũ của là ; nhận màu cũ của là ; cuối cùng nhận .
graph 1 2 2 1 5 1 2 4 3 3 4 1 3 5 3 4 5 2 pos 1 0 0 pos 2 160 0 pos 5 0 150 pos 3 80 230 pos 4 160 150 step Sau khi lật đường 4-3-5 và xoay quạt 5, 3, 2 highlight purple 3-5 highlight orange 4-5 4-3 4-2
Kết quả: , , , , , . Đỉnh có màu ; đỉnh có màu ; hợp lệ. Lần này thuật toán chỉ dùng màu, nhưng nó chỉ đảm bảo .
Cài đặt
Đồ thị hai phía với đúng màu
Input: dòng đầu (số đỉnh trái, phải, số cạnh), dòng tiếp theo mỗi dòng là cạnh nối đỉnh trái với đỉnh phải (cho phép cạnh bội). Output: , rồi màu (từ ) của từng cạnh theo thứ tự input. Bảng at[x][c] lưu chỉ số cạnh màu tại nên cạnh bội không gây nhầm lẫn.
#include <bits/stdc++.h>
using namespace std;
// Edge coloring of a bipartite (multi)graph with exactly Delta colors (Konig).
// Vertices: left 0..L-1, right L..L+R-1. Colors 0..D-1.
int main() {
int L, R, m;
scanf("%d %d %d", &L, &R, &m);
int n = L + R;
vector<int> eu(m), ev(m), deg(n, 0);
for (int i = 0; i < m; i++) {
scanf("%d %d", &eu[i], &ev[i]);
eu[i]--; ev[i] = L + ev[i] - 1;
deg[eu[i]]++; deg[ev[i]]++;
}
int D = 0;
for (int x : deg) D = max(D, x);
// at[x][c] = id of the edge with color c at vertex x, or -1
vector<vector<int>> at(n, vector<int>(max(D, 1), -1));
vector<int> color(m, -1);
auto other = [&](int e, int x) { return eu[e] == x ? ev[e] : eu[e]; };
auto freeColor = [&](int x) {
int c = 0;
while (at[x][c] != -1) c++;
return c;
};
for (int e = 0; e < m; e++) {
int u = eu[e], v = ev[e];
int a = freeColor(u), b = freeColor(v);
if (at[v][a] != -1) {
// a is busy at v: walk the path from v whose colors alternate a, b, a, ...
vector<int> path;
int x = v, c = a;
while (at[x][c] != -1) {
int f = at[x][c];
path.push_back(f);
x = other(f, x);
c = (c == a) ? b : a;
}
// swap a <-> b on the whole path (clear first, then repaint)
for (int f : path) at[eu[f]][color[f]] = at[ev[f]][color[f]] = -1;
for (int f : path) {
color[f] = (color[f] == a) ? b : a;
at[eu[f]][color[f]] = at[ev[f]][color[f]] = f;
}
}
// now a is free at both u and v
color[e] = a;
at[u][a] = at[v][a] = e;
}
printf("%d\n", D);
for (int e = 0; e < m; e++) printf("%d%c", color[e] + 1, e + 1 == m ? '\n' : ' ');
}
import sys
def main():
data = sys.stdin.buffer.read().split()
L, R, m = int(data[0]), int(data[1]), int(data[2])
n = L + R
eu, ev = [0] * m, [0] * m
deg = [0] * n
for i in range(m):
eu[i] = int(data[3 + 2 * i]) - 1
ev[i] = L + int(data[4 + 2 * i]) - 1
deg[eu[i]] += 1
deg[ev[i]] += 1
D = max(deg) if n else 0
at = [[-1] * max(D, 1) for _ in range(n)] # at[x][c] = edge id with color c at x
color = [-1] * m
def free_color(x):
row = at[x]
c = 0
while row[c] != -1:
c += 1
return c
for e in range(m):
u, v = eu[e], ev[e]
a, b = free_color(u), free_color(v)
if at[v][a] != -1:
# walk the a/b alternating path from v and swap a <-> b on it
path, x, c = [], v, a
while at[x][c] != -1:
f = at[x][c]
path.append(f)
x = ev[f] if eu[f] == x else eu[f]
c = b if c == a else a
for f in path:
at[eu[f]][color[f]] = at[ev[f]][color[f]] = -1
for f in path:
color[f] = b if color[f] == a else a
at[eu[f]][color[f]] = at[ev[f]][color[f]] = f
color[e] = a
at[u][a] = at[v][a] = e
print(D)
print(" ".join(str(c + 1) for c in color))
main()
Với ví dụ chạy tay ở trên:
3 3 6
3 1
1 2
1 1
2 2
2 3
1 3
chương trình in ra
3
2 2 1 1 2 3
đúng với kết quả , , , , , .
Vizing với tối đa màu
Input: dòng đầu , dòng tiếp theo mỗi dòng là một cạnh của đồ thị đơn. Output: số màu thực sự dùng (không quá ), rồi màu từng cạnh. Vì đồ thị đơn nên nb[x][c] lưu luôn đỉnh kề qua màu , đủ để xác định cạnh. Mảng freeC[x] giữ sẵn một màu rảnh tại và chỉ được tính lại ở vài đỉnh thay đổi, nhờ đó dựng quạt tốn thay vì .
#include <bits/stdc++.h>
using namespace std;
// Vizing: edge coloring of a simple graph with at most Delta + 1 colors, O(n * m).
int n, m, C; // C = Delta + 1 colors: 0..C-1
vector<vector<int>> nb; // nb[x][c] = neighbor joined to x by the edge of color c, or -1
vector<int> freeC; // freeC[x] = some color that is free at x
vector<int> colU; // colU[y] = color of edge (u, y) for the current u
void paint(int x, int y, int c) { nb[x][c] = y; nb[y][c] = x; }
int recompute(int x) { int c = 0; while (nb[x][c] != -1) c++; return c; }
void addEdge(int u, int v) {
// 1. Build the fan f0 = v, f1, f2, ...: color(u, f[i+1]) is free at f[i].
vector<int> fan = {v};
vector<char> inFan(n, 0);
inFan[v] = 1;
int d;
while (true) {
d = freeC[fan.back()];
int x = nb[u][d];
if (x == -1 || inFan[x]) break;
fan.push_back(x);
inFan[x] = 1;
}
// d is free at the last fan vertex; c is free at u
int c = freeC[u];
// 2. Invert the c/d path that starts at u (its first edge has color d).
vector<array<int, 3>> path; // (x, y, color)
int x = u, col = d, end = u;
while (nb[x][col] != -1) {
int y = nb[x][col];
path.push_back({x, y, col});
x = y; end = y;
col = (col == c) ? d : c;
}
for (auto [p, q, k] : path) nb[p][k] = nb[q][k] = -1;
for (auto [p, q, k] : path) paint(p, q, k == c ? d : c);
if (end != u) freeC[end] = recompute(end);
// 3. Rotate the fan up to the first vertex w where d is free, then color (u, w) with d.
for (int k = 0; k < C; k++)
if (nb[u][k] != -1) colU[nb[u][k]] = k;
int i = 0;
while (nb[fan[i]][d] != -1) {
int left = fan[i], right = fan[i + 1];
int k = colU[right]; // k = color(u, right)
nb[right][k] = -1; // right loses color k
paint(u, left, k); // left takes color k
freeC[right] = k;
i++;
}
paint(u, fan[i], d);
freeC[u] = recompute(u);
freeC[v] = recompute(v);
freeC[fan[i]] = recompute(fan[i]);
}
int main() {
scanf("%d %d", &n, &m);
vector<int> eu(m), ev(m), deg(n, 0);
for (int i = 0; i < m; i++) {
scanf("%d %d", &eu[i], &ev[i]);
eu[i]--; ev[i]--;
deg[eu[i]]++; deg[ev[i]]++;
}
C = *max_element(deg.begin(), deg.end()) + 1;
nb.assign(n, vector<int>(C, -1));
freeC.assign(n, 0);
colU.assign(n, 0);
for (int i = 0; i < m; i++) addEdge(eu[i], ev[i]);
int used = 0;
vector<int> color(m);
for (int i = 0; i < m; i++) {
int k = 0;
while (nb[eu[i]][k] != ev[i]) k++;
color[i] = k;
used = max(used, k + 1);
}
printf("%d\n", used);
for (int i = 0; i < m; i++) printf("%d%c", color[i] + 1, i + 1 == m ? '\n' : ' ');
}
import sys
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
eu = [int(data[2 + 2 * i]) - 1 for i in range(m)]
ev = [int(data[3 + 2 * i]) - 1 for i in range(m)]
deg = [0] * n
for i in range(m):
deg[eu[i]] += 1
deg[ev[i]] += 1
C = max(deg) + 1
nb = [[-1] * C for _ in range(n)] # nb[x][c] = neighbor via color c, or -1
free = [0] * n # free[x] = some free color at x
col_u = [0] * n
def first_free(x):
row = nb[x]
c = 0
while row[c] != -1:
c += 1
return c
for u, v in zip(eu, ev):
# 1. maximal fan around u starting at v
fan, in_fan = [v], {v}
while True:
d = free[fan[-1]]
x = nb[u][d]
if x == -1 or x in in_fan:
break
fan.append(x)
in_fan.add(x)
c = free[u]
# 2. invert the c/d path starting at u
path, x, k, end = [], u, d, u
while nb[x][k] != -1:
y = nb[x][k]
path.append((x, y, k))
x = end = y
k = d if k == c else c
for p, q, k in path:
nb[p][k] = nb[q][k] = -1
for p, q, k in path:
k2 = d if k == c else c
nb[p][k2], nb[q][k2] = q, p
if end != u:
free[end] = first_free(end)
# 3. rotate the fan until a vertex with d free, then color (u, w) with d
for k in range(C):
if nb[u][k] != -1:
col_u[nb[u][k]] = k
i = 0
while nb[fan[i]][d] != -1:
left, right = fan[i], fan[i + 1]
k = col_u[right]
nb[right][k] = -1
nb[u][k], nb[left][k] = left, u
free[right] = k
i += 1
w = fan[i]
nb[u][d], nb[w][d] = w, u
for y in (u, v, w):
free[y] = first_free(y)
color = []
for a, b in zip(eu, ev):
k = 0
while nb[a][k] != b:
k += 1
color.append(k)
print(max(color) + 1 if m else 0)
print(" ".join(str(k + 1) for k in color))
main()
Với ví dụ Vizing ở trên (thứ tự cạnh ):
5 6
4 2
1 5
1 2
4 3
3 5
4 5
chương trình in ra
3
3 1 2 1 3 2
khớp với kết quả chạy tay: , , , , , .
Kiểm tra kết quả
Đáp án tô màu cạnh thường không duy nhất nên đề dùng checker. Khi tự kiểm thử, viết một checker ngắn: mọi màu nằm trong , (hai phía) hoặc (Vizing), và không đỉnh nào có hai cạnh cùng màu. Cả hai chương trình trên (C++ và Python) đã được chạy trên vài nghìn đồ thị ngẫu nhiên (hai phía có cạnh bội, đồ thị đơn với mật độ khác nhau) và đều qua checker này.
def check(n, edges, colors, limit):
"""edges: list of (u, v); colors: list of ints from 1; limit: Delta or Delta + 1."""
seen = set()
for (u, v), c in zip(edges, colors):
if not 1 <= c <= limit:
return False
for x in (u, v):
if (x, c) in seen:
return False # two edges of color c meet at x
seen.add((x, c))
return True
Độ phức tạp
- Hai phía (Kőnig). Mỗi cạnh: tìm màu rảnh , đi và lật đường xen kẽ vì đường đi qua mỗi đỉnh nhiều nhất một lần. Tổng thời gian. Bộ nhớ cho bảng
at, cộng . - Vizing. Mỗi cạnh: dựng quạt (mỗi đỉnh quạt tra
freeC, quạt có không quá đỉnh), lật đường , xoay quạt , tính lại màu rảnh ở vài đỉnh . Tổng . Bộ nhớ .
Thực tế đường xen kẽ thường ngắn hơn nhiều so với , nên cả hai chạy nhanh với vài nghìn, vài trăm nghìn. Có thuật toán nhanh hơn cho đồ thị hai phía, (Cole, Ost, Schirra), dựa trên chia đôi Euler; hiếm khi cần trong thi đấu.
⚠️ Lỗi thường gặp
- Dùng Vizing cho đồ thị có cạnh bội. Định lý Vizing dạng chỉ đúng cho đồ thị đơn. Đồ thị có cạnh bội có thể cần tới màu (định lý Shannon), ví dụ "tam giác" mỗi cặp đỉnh nối cạnh có nhưng cần màu. Code Vizing ở trên lưu
nb[x][c]là đỉnh, gặp cạnh bội sẽ sai. Trái lại, đồ thị hai phía có cạnh bội vẫn cần đúng màu và code Kőnig ở trên xử lý được vì lưu chỉ số cạnh. - Lật đường nhầm chiều hoặc nhầm màu bắt đầu. Ở thuật toán hai phía, đường phải bắt đầu từ bằng màu (màu rảnh tại ). Nếu bắt đầu từ bằng màu thì cũng đúng (đối xứng), nhưng trộn hai cách, ví dụ bắt đầu từ bằng màu , thì vòng lặp dừng ngay vì rảnh tại , và cạnh bị tô trùng màu.
- Đổi màu tại chỗ khi đang duyệt đường. Gán
at[x][newColor] = fngay trong lúc đi có thể ghi đè ô mà bước sau còn cần đọc. Thu thập cả đường trước, xóa hết rồi mới tô lại, như trong code. - Tưởng thuật toán Vizing cho số màu tối ưu. Nó luôn dùng không quá màu nhưng có thể dùng ngay cả khi đồ thị thuộc lớp 1. Quyết định hay là NP-khó; nếu đề yêu cầu tối ưu trên đồ thị tổng quát thì phải tìm cấu trúc đặc biệt (hai phía, cây, , nhỏ để duyệt), không phải chạy Vizing.
- Bảng màu cấp thiếu một ô. Thuật toán hai phía cần đúng cột, Vizing cần cột. Cấp cột cho Vizing thì
recomputechạy tràn mảng khi đỉnh đã đủ cạnh. Cũng chú ý (không có cạnh): dùngmax(D, 1)để tránh vector rỗng. - Mảng quá lớn. Với và bảng có ô. Khi đó dùng bảng màu theo cạnh (
maphayunordered_maptheo từng đỉnh) hoặc kiểm tra lại giới hạn: các bài tô màu cạnh tổng quát thường có nhỏ. - Quên rằng mỗi lớp màu là một cặp ghép. Nhiều bài không nói "tô màu" mà nói "số ngày ít nhất để mỗi đội đá một trận mỗi ngày", "số lượt ít nhất mỗi máy xử lý một việc mỗi lượt". Nhận ra mô hình cạnh và chặn dưới là bước quan trọng nhất.
Ứng dụng và mở rộng
- Xếp lịch thi đấu. Mỗi đội là đỉnh, mỗi trận là cạnh, mỗi vòng đấu là một màu. Số vòng ít nhất là . Với giải vòng tròn đội (): vòng khi chẵn, vòng khi lẻ. Có công thức trực tiếp (phương pháp vòng tròn): với chẵn, đánh số đội và cố định đội ; ở vòng cho đội gặp đội , và đội gặp đội với . Với lẻ thêm một đội "nghỉ".
- Lịch giáo viên và lớp học (open shop). Giáo viên là phía trái, lớp là phía phải, mỗi tiết phải dạy là một cạnh (có thể nhiều cạnh giữa cùng một cặp). Số tiết ít nhất của thời khóa biểu bằng bậc lớn nhất theo định lý Kőnig cho đa đồ thị hai phía.
- Tách đồ thị hai phía chính quy thành cặp ghép hoàn hảo. Đồ thị hai phía -chính quy tô bằng màu, mỗi màu là một cặp ghép hoàn hảo. Ứng dụng điển hình: hoàn thiện hình vuông Latin (mỗi ô trống là một cạnh hàng, cột; mỗi giá trị còn thiếu là một màu). Một cách khác là tìm lần lượt cặp ghép hoàn hảo bằng ghép cặp hai phía hoặc Hopcroft-Karp, mỗi lần bỏ cặp ghép tìm được thì đồ thị vẫn chính quy với bậc giảm .
- Khi là lũy thừa của 2. Đồ thị hai phía -chính quy có thể tách đôi bằng chu trình Euler: đi theo chu trình Euler và tô xen kẽ hai màu, mỗi đỉnh nhận đúng một nửa số cạnh mỗi màu. Lặp lại lần được .
- Cây và rừng là đồ thị hai phía, nên luôn tô được bằng màu. Trên cây có cách đơn giản hơn: DFS từ gốc, các cạnh xuống con của đỉnh lần lượt nhận các màu bỏ qua màu của cạnh từ lên cha.
Bài tập luyện
- Hình vuông Latin (icpc19regl) (Rất khó): các ô trống tạo thành đồ thị hai phía hàng, cột -chính quy; tô màu cạnh bằng màu (hoặc tách thành cặp ghép hoàn hảo) cho ngay cách điền các giá trị còn thiếu, và đáp án luôn là YES.
Hiện kho bài CTOJ mới có một bài dùng đúng kỹ thuật này; các bài tô màu cạnh khác (xếp lịch thi đấu, tô cạnh cây theo bậc) sẽ được bổ sung khi có.
Bình luận