Chỉ số màu (chromatic index) là số màu tối đa cần cho việc tô màu cạnh của đồ thị cho trước. Đây là chương trình C++ tìm chỉ số màu của đồ thị chu trình (cyclic graphs).
Thuật toán
Bắt đầu
Nhập số đỉnh 'n' và số cạnh 'e'.
Nhập 'e' cặp đỉnh cho 'e' cạnh trong edge[][].
Hàm ChromaticIndex(), tô màu cạnh:
A) Gán màu cho cạnh hiện tại là c.
B) Nếu cạnh kề nào cùng màu thì loại bỏ màu đó, quay lại flag thử màu tiếp.
C) In chỉ số màu của đồ thị chu trình.
In màu của mỗi cạnh.
Kết thúc
Ví dụ mã nguồn
#include <iostream>
using namespace std;
int ChromaticIndex(int ed[][3], int e) {
int i, c, j, max = -1;
// gán màu hợp lệ cho mỗi cạnh i
for (i = 0; i < e; i++) {
c = 1;
flag:
ed[i][2] = c;
for (j = 0; j < e; j++) {
if (j == i) continue;
// kiểm tra màu các cạnh kề cạnh i
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;
}
}
}
}
// tìm chỉ số màu và trả về
for (i = 0; i < e; i++) {
if (max < ed[i][2])
max = ed[i][2];
}
return max;
}
int main() {
int i, v, e, j, max = -1;
cout << "Nhập số đỉnh của đồ thị: ";
cin >> v;
cout << "Nhập số cạnh của đồ thị: ";
cin >> e;
int ed[e][3];
for (i = 0; i < e; i++) {
cout << "\nNhập cặp đỉnh cho cạnh " << i+1;
cout << "\nV(1): ";
cin >> ed[i][0];
cout << "V(2): ";
cin >> ed[i][1];
ed[i][2] = -1;
}
cout << "\n\nChỉ số màu của đồ thị cho trước là: " << ChromaticIndex(ed, e);
for (i = 0; i < e; i++)
cout << "\nMàu cạnh giữa đỉnh n(1):" << ed[i][0] << " và n(2):" << ed[i][1] << " là: color" << ed[i][2] << ".";
return 0;
}
Kết quả
Nhập số đỉnh của đồ thị: 4 Nhập số cạnh của đồ thị: 5 Nhập cặp đỉnh cho cạnh 1 V(1): 2 V(2): 1 Nhập cặp đỉnh cho cạnh 2 V(1): 3 V(2): 2 Nhập cặp đỉnh cho cạnh 3 V(1): 3 V(2): 1 Nhập cặp đỉnh cho cạnh 4 V(1): 4 V(2): 2 Nhập cặp đỉnh cho cạnh 5 V(1): 1 V(2): 3 Chỉ số màu của đồ thị cho trước là: 4 Màu cạnh giữa đỉnh n(1):2 và n(2):1 là: color1. Màu cạnh giữa đỉnh n(1):3 và n(2):2 là: color2. Màu cạnh giữa đỉnh n(1):3 và n(2):1 là: color3. Màu cạnh giữa đỉnh n(1):4 và n(2):2 là: color3. Màu cạnh giữa đỉnh n(1):1 và n(2):3 là: color4.