Chương trình C++ triển khai định lý Vizing cho tô màu cạnh

Định lý Vizing phát biểu rằng chỉ số tô màu (chromatic index) của một đồ thị đơn giản bằng bậc lớn nhất (Δ) hoặc Δ+1. Chương trình này minh họa việc tô màu cạnh theo định lý này.

Thuật toán

Bắt đầu
  Nhập số đỉnh (n) và số cạnh (e).
  Nhập cặp đỉnh cho từng cạnh.
  Hàm EdgeColor(): Tô màu các cạnh.
    1) Gán màu cho cạnh hiện tại là c = 1.
    2) Nếu màu c đã được dùng bởi cạnh kề, bỏ qua và thử màu tiếp theo (c++).
    3) Lặp lại cho tất cả các cạnh.
Kết thúc

Ví dụ mã nguồn

#include <iostream>
using namespace std;

void EdgeColor(int ed[][3], int e) {
    for (int i = 0; i < e; i++) {
        int c = 1;
        flag:
        ed[i][2] = c;
        for (int j = 0; j < e; j++) {
            if (j == i) continue;
            if (ed[j][0] == ed[i][0] || ed[j][0] == ed[i][1] ||
                ed[j][1] == ed[i][0] || ed[j][1] == ed[i][1]) {
                if (ed[j][2] == ed[i][2]) {
                    c++;
                    goto flag;
                }
            }
        }
    }
}

int main() {
    int n, e;
    cout << "So dinh: "; cin >> n;
    cout << "So canh: "; cin >> e;
    
    int ed[e][3], deg[n+1] = {0};
    for (int i = 0; i < e; i++) {
        cout << "Canh " << i+1 << ": ";
        cin >> ed[i][0] >> ed[i][1];
        ed[i][2] = -1;
        deg[ed[i][0]]++;
        deg[ed[i][1]]++;
    }
    
    int maxDeg = 0;
    for (int i = 1; i <= n; i++)
        if (deg[i] > maxDeg) maxDeg = deg[i];
    
    EdgeColor(ed, e);
    
    cout << "\nTheo dinh ly Vizing, do thi nay can toi da " << maxDeg+1 << " mau.\n";
    for (int i = 0; i < e; i++)
        cout << "Canh (" << ed[i][0] << "," << ed[i][1] << "): mau " << ed[i][2] << ".\n";
    return 0;
}

Đầu ra mẫu

So dinh: 4
So canh: 3
Canh 1: 1 2
Canh 2: 3 2
Canh 3: 4 1
Theo dinh ly Vizing, do thi nay can toi da 3 mau.
Canh (1,2): mau 1.
Canh (3,2): mau 2.
Canh (4,1): mau 2.