Wiki › Thuật toán › Thuật toán đồ thị › Tô màu cạnh (Kőnig và Vizing)

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).

huunguyen huunguyen Updated Tháng 11. 17, 2026 Đọc 26 phút 4 lượt xem

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). Gọi Δ là bậc lớn nhất của đồ thị: hiển nhiên χ′(G)≥Δ, 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 Δ+1 màu). Cả hai đều cài được trong O(n·m), 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 k màu chính là chia tập cạnh thành k 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 x, màu c gọi là rảnh tại x (free) nếu không cạnh nào đã tô tại x mang màu c.

Khi thêm cạnh (u,v) chưa tô: u đang có tối đa deg(u)−1≤Δ−1 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 u, tương tự tại v. 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 u đang bận tại v và ngược lại. Công cụ chung để gỡ là đường xen kẽ.

Đường xen kẽ hai màu (a/b-path)

Lấy hai màu a,b và chỉ nhìn các cạnh màu a hoặc b. Mỗi đỉnh có nhiều nhất một cạnh màu a và một cạnh màu b, nên đồ thị con này có bậc ≤2: nó gồm các đường đi và chu trình rời nhau, màu trên mỗi đường xen kẽ a,b,a,b,…

Đổi màu cả một thành phần (mọi a thành b, mọi b thành a) vẫn cho cách tô hợp lệ: đỉnh trong của đường vẫn có đúng một cạnh a và một cạnh b; đỉ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ừ a sang b 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), χ′(G)=Δ.

Chứng minh có tính xây dựng. Dùng bảng Δ màu. Thêm cạnh (u,v) với u ở phía trái, v ở phía phải. Chọn a rảnh tại u, b rảnh tại v.

  • Nếu a cũng rảnh tại v: tô (u,v) màu a.
  • Ngược lại, xét đường xen kẽ a/b bắt đầu từ v: đi theo cạnh màu a ra khỏi v, rồi cạnh màu b, rồi a... (v không có cạnh b nên v là đầu mút). Đường này không bao giờ chạm u. Thật vậy, cạnh thứ 1,3,5,… màu a, cạnh thứ 2,4,… màu b. Vì a rảnh tại u, nếu đường tới u thì nó phải tới qua một cạnh màu b, tức là sau một số chẵn cạnh. Nhưng u và v ở hai phía khác nhau, mọi đường từ v tới u đều có độ dài lẻ. Mâu thuẫn.
  • Lật đường đó. Tại v, cạnh màu a thành màu b (đúng màu đang rảnh tại v), nên a trở thành rảnh tại v. Tại u không có gì thay đổi vì u không nằm trên đường. Giờ a rảnh ở cả hai đầu, tô (u,v) màu a.

Mỗi cạnh luôn tô được bằng một trong Δ màu, nên χ′(G)≤Δ; kết hợp chặn dưới ta có đẳng thức.

Hệ quả. Đồ thị hai phía k-chính quy (mọi đỉnh bậc k) tách được thành k 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ó đủ k cạnh với k màu khác nhau.

Vì sao đồ thị tổng quát có thể cần Δ+1

Tam giác K3 có Δ=2 nhưng ba cạnh đôi một chung đỉnh, nên cần 3 màu. Chứng minh Kőnig hỏng đúng ở chỗ dùng tính chẵn lẻ: trong chu trình lẻ, đường a/b từ v có thể quay về u.

Các đồ thị đầy đủ: χ′(Kn)=n−1 khi n chẵn và χ′(Kn)=n khi n lẻ. Với n lẻ, mỗi lớp màu ghép được nhiều nhất n−12 cạnh, cần ít nhất n(n−1)/2(n−1)/2=n=Δ+1 màu. Đồ thị Petersen (Δ=3) cũng cần 4 màu.

Định lý Vizing: Δ hoặc Δ+1

Định lý (Vizing, 1964). Với đồ thị đơn (không cạnh bội, không khuyên), Δ≤χ′(G)≤Δ+1.

Đồ thị có χ′=Δ gọi là lớp 1, có χ′=Δ+1 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ị 3-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 Δ+1 màu.

Thuật toán xây dựng (Misra và Gries). Dùng bảng Δ+1 màu. Bây giờ mỗi đỉnh x luôn có ít nhất một màu rảnh, kể cả khi mọi cạnh tại x đã tô (deg(x)≤Δ<Δ+1). Thêm cạnh (u,v):

  1. Dựng quạt (fan) quanh u: dãy đỉnh f0=v,f1,…,fk là các hàng xóm phân biệt của u sao cho với mọi i, màu của cạnh (u,fi+1) rảnh tại fi. Cách dựng: lấy d là một màu rảnh tại fcuối; nếu u có cạnh màu d tới một đỉnh x chưa trong quạt thì thêm x vào quạt và lặp lại; nếu không thì dừng. Khi dừng, d rảnh tại fk và hoặc d rảnh tại u, hoặc d là màu của cạnh (u,fj) với một j≥1 nào đó.
  2. Xoay quạt (rotate) là thao tác then chốt: nếu d rảnh tại fi thì ta có thể tô (u,f0) bằng màu của (u,f1), tô (u,f1) bằng màu của (u,f2), ..., tô (u,fi−1) bằng màu của (u,fi), bỏ màu (u,fi) rồi tô nó bằng d. Mỗi bước hợp lệ vì màu của (u,ft+1) rảnh tại ft (định nghĩa quạt). Bước cuối cần d rảnh tại cả u và fi.
  3. Làm d rảnh tại u. Lấy c là một màu rảnh tại u. Lật đường xen kẽ c/d bắt đầu từ u (đường này bắt đầu bằng cạnh màu d nếu có). Sau khi lật, d rảnh tại u.
  4. Chọn w là đỉnh đầu tiên của quạt mà d rảnh. Xoay quạt từ f0 tới w rồi tô (u,w) màu d.

Vì sao bước 4 luôn tìm được w hợp lệ. Trường hợp d rảnh tại u từ đầu thì đường ở bước 3 rỗng, fk có d rảnh. Trường hợp d là màu của (u,fj): theo định nghĩa quạt, d rảnh tại fj−1, và cũng rảnh tại fk. Đường c/d từ u đi qua fj 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ả fj−1 lẫn fk:

  • Nếu đường không kết thúc ở fj−1: sau khi lật d vẫn rảnh tại fj−1. Phần quạt f0..fj−1 không bị ảnh hưởng (màu các cạnh (u,ft) với t<j không phải c hay d), nên w nằm trong đoạn này.
  • Nếu đường kết thúc ở fj−1: nó tới fj−1 qua một cạnh màu c, lật xong cạnh đó thành d nên c rảnh tại fj−1. Mà cạnh (u,fj) giờ mang màu c, nên toàn bộ quạt vẫn hợp lệ, và d vẫn rảnh tại fk (đường không kết thúc ở đó).

Trong cả hai trường hợp, đoạn quạt từ f0 tới w hợp lệ và d rảnh tại u lẫn w, nên bước xoay thành công. Cạnh nào cũng tô được bằng Δ+1 màu.

Ví dụ chạy tay

Kőnig: một lần lật đường

Đồ thị hai phía trái {1,2,3}, phải {a,b,c}, các cạnh theo thứ tự thêm vào: 3a,1b,1a,2b,2c,1c. Đỉnh 1 có bậc 3 nên Δ=3, dùng màu {1,2,3}. 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
3a 1 1 trùng, tô luôn 1
1b 1 1 trùng, tô luôn 1
1a 2 2 trùng, tô luôn 2
2b a=1 b=2 màu 1 bận tại b, lật đường 1/2 từ b 1
2c 2 1 màu 2 rảnh tại c, tô luôn 2
1c 3 1 màu 3 rảnh tại c, tô luôn 3

Ở cạnh 2b: màu 1 rảnh tại 2 nhưng b đã có cạnh 1b màu 1. Đường xen kẽ 1/2 từ b là b→11→2a→13 (đỉnh 3 không có cạnh màu 2 nên dừng). Đường dài 3 (lẻ) và kết thúc ở phía trái tại đỉnh 3≠2, đúng như chứng minh. Lật đường: 1b thành 2, 1a thành 1, 3a thành 2. Giờ màu 1 rảnh tại b, tô 2b màu 1.

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ả: 3a=2, 1b=2, 1a=1, 2b=1, 2c=2, 1c=3. Đỉnh 1 có ba cạnh màu 1,2,3; mọi đỉnh khác có các cạnh khác màu.

Vizing: quạt, lật đường và xoay

Đồ thị đơn 5 đỉnh, Δ=3, bảng màu {1,2,3,4}. Năm cạnh đầu đã được tô; ta xem bước thêm cạnh cuối (4,5) với u=4, v=5. 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 u=4 (các cạnh tại 4: (4,2)=1, (4,3)=3, nên màu rảnh nhỏ nhất tại 4 là c=2).

Đỉnh quạt Màu tại đỉnh Màu rảnh d Cạnh của 4 mang màu d Hành động
f0=5 1,2 3 (4,3) thêm f1=3
f1=3 3,2 1 (4,2) thêm f2=2
f2=2 2,1 3 (4,3), nhưng 3 đã trong quạt dừng, d=3

Vậy d=3 là màu của (u,f1), tức j=1, và d rảnh tại fj−1=f0=5.

Bước 2: lật đường c/d=2/3 từ u=4. Đường là 4→33→25, dừng ở 5 vì 5 không có cạnh màu 3. Đường kết thúc đúng ở fj−1=5 (trường hợp thứ hai của chứng minh). Lật xong: (4,3)=2, (3,5)=3. Bây giờ d=3 rảnh tại 4.

Bước 3: tìm w là đỉnh quạt đầu tiên có màu 3 rảnh: f0=5 vừa nhận màu 3 (cạnh 3-5), f1=3 cũng có màu 3, f2=2 có màu {2,1} nên w=f2=2.

Bước 4: xoay quạt từ f0 tới f2: (4,5) nhận màu cũ của (4,3) là 2; (4,3) nhận màu cũ của (4,2) là 1; cuối cùng (4,2) nhận d=3.

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ả: (1,2)=2, (1,5)=1, (2,4)=3, (3,4)=1, (3,5)=3, (4,5)=2. Đỉnh 4 có màu 3,1,2; đỉnh 5 có màu 1,3,2; hợp lệ. Lần này thuật toán chỉ dùng 3=Δ màu, nhưng nó chỉ đảm bảo Δ+1.

Cài đặt

Đồ thị hai phía với đúng Δ màu

Input: dòng đầu L R m (số đỉnh trái, phải, số cạnh), m dòng tiếp theo mỗi dòng a b là cạnh nối đỉnh trái a với đỉnh phải b (cho phép cạnh bội). Output: Δ, rồi màu (từ 1) của từng cạnh theo thứ tự input. Bảng at[x][c] lưu chỉ số cạnh màu c tại x nên cạnh bội không gây nhầm lẫn.

C++
#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' : ' ');
}
Python
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ả 3a=2, 1b=2, 1a=1, 2b=1, 2c=2, 1c=3.

Vizing với tối đa Δ+1 màu

Input: dòng đầu n m, m dòng tiếp theo mỗi dòng u v là một cạnh của đồ thị đơn. Output: số màu thực sự dùng (không quá Δ+1), 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 c, đủ để xác định cạnh. Mảng freeC[x] giữ sẵn một màu rảnh tại x và chỉ được tính lại ở vài đỉnh thay đổi, nhờ đó dựng quạt tốn O(Δ) thay vì O(Δ2).

C++
#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' : ' ');
}
Python
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 (4,2),(1,5),(1,2),(4,3),(3,5),(4,5)):

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: (4,2)=3, (1,5)=1, (1,2)=2, (4,3)=1, (3,5)=3, (4,5)=2.

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 [1,K], K≤Δ (hai phía) hoặc K≤Δ+1 (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 O(Δ), đi và lật đường xen kẽ O(n) vì đường đi qua mỗi đỉnh nhiều nhất một lần. Tổng O(m(n+Δ))=O(n·m) thời gian. Bộ nhớ O(n·Δ) cho bảng at, cộng O(m).
  • Vizing. Mỗi cạnh: dựng quạt O(Δ) (mỗi đỉnh quạt tra freeC O(1), quạt có không quá deg(u) đỉnh), lật đường O(n), xoay quạt O(Δ), tính lại màu rảnh ở vài đỉnh O(Δ). Tổng O(m(n+Δ))=O(n·m). Bộ nhớ O(n·Δ).

Thực tế đường xen kẽ thường ngắn hơn nhiều so với n, nên cả hai chạy nhanh với n vài nghìn, m vài trăm nghìn. Có thuật toán nhanh hơn cho đồ thị hai phía, O(mlogΔ) (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 Δ+1 chỉ đúng cho đồ thị đơn. Đồ thị có cạnh bội có thể cần tới ⌊3Δ/2⌋ màu (định lý Shannon), ví dụ "tam giác" mỗi cặp đỉnh nối k cạnh có Δ=2k nhưng cần 3k 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ừ v bằng màu a (màu rảnh tại u). Nếu bắt đầu từ u bằng màu b thì cũng đúng (đối xứng), nhưng trộn hai cách, ví dụ bắt đầu từ v bằng màu b, thì vòng lặp dừng ngay vì b rảnh tại v, 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] = f ngay 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á Δ+1 màu nhưng có thể dùng Δ+1 ngay cả khi đồ thị thuộc lớp 1. Quyết định Δ hay Δ+1 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, Kn, n 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 Δ+1 cột. Cấp Δ cột cho Vizing thì recompute chạy tràn mảng khi đỉnh đã đủ Δ cạnh. Cũng chú ý Δ=0 (không có cạnh): dùng max(D, 1) để tránh vector rỗng.
  • Mảng n×Δ quá lớn. Với n=2·105 và Δ=105 bảng có 2·1010 ô. Khi đó dùng bảng màu theo cạnh (map hay unordered_map theo 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ó n·Δ 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 n đội (Kn): n−1 vòng khi n chẵn, n vòng khi n lẻ. Có công thức trực tiếp (phương pháp vòng tròn): với n chẵn, đánh số đội 0..n−1 và cố định đội n−1; ở vòng r=0..n−2 cho đội n−1 gặp đội r, và đội (r+i)mod(n−1) gặp đội (r−i)mod(n−1) với i=1..n2−1. Với n 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 k-chính quy tô bằng k 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 k 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 1.
  • Khi Δ là lũy thừa của 2. Đồ thị hai phía 2t-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 t lần được O(mlogΔ).
  • 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 x lần lượt nhận các màu 1,2,… bỏ qua màu của cạnh từ x 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 (n−k)-chính quy; tô màu cạnh bằng n−k màu (hoặc tách thành n−k 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ó.

Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0