Tài liệu hướng dẫn thực hành
1
BÀI TOÁN TÔ MÀU

Văn Chí Nam – Nguyễn Đức Hoàng Hạ
Lu Boun Vinh – Nguyễn Anh Tuấn
Khoa Công nghệ Thông tin, trường ĐH Khoa học Tự nhiên TP.HCM
Phiên bản cập nhật ngày 18/10/2004
Thuật toán
Bước 1. Tìm đỉnh k có bậc cao nhất và chưa được tô.
Bước 2. Nếu không tìm được k thì dừng, ngược lại qua bước 2.
Bước 2. Tô màu m cho đỉnh k (m là màu nhỏ nhất chưa bị cấm khi tô đỉnh k).
Bước 3. Hạ bậc các đỉnh có cung nối với k.
Bước 4. Quay lại bước 1.
Cấu trúc dữ liệu đề nghị
1

typedef struct {
int Bac;
int MauTo;
int MauCam[MAXMAU];
}DINH;

DINH D[MAX];
int n;
int A[MAX][MAX];

Ý nghĩa:
Bac: bậc của đỉnh
MauTo: nếu MauTo = -1 thì đỉnh chưa được tô. Ngược lại đỉnh được tô bằng
MauTo.

A[MAX][MAX])
{
m là màu nhỏ nhất mà D[i].MauCam[m]=0
Tô màu đỉnh i: D[i].MauTo = m
Hạ bậc và cấm tô màu m các đỉnh có quan hệ với i.
}
Hàm tô màu các đỉnh
void ToMau(DINH D[MAX], int n, int A[MAX][MAX])
{
KhoiTao( )
while (còn đỉnh chưa tô)
{
k = đỉnh chưa tô có bậc lớn nhất.
Tô màu đỉnh k.
}
}
Mở rộng

- Áp dụng kết hợp với phương pháp Greedy.
- Cải tiến cài đặt cho trường hợp đồ thị lớn (n>200).
- Cài đặt giao diện cho ứng dụng.