Tài liệu hướng dẫn thực hành Bài toán tô màu

Thuật toánBướ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.
Nội dung trích xuất từ tài liệu:
Tài liệu hướng dẫn thực hành Bài toán tô màu Tài liệu hướng dẫn thực hành 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ằngMauTo. MauCam[]: - MauCam[i] = 0: đỉnh không bị cấm tô màu i. - MauCam[i] = 1: đỉnh bị bị cấm tô màu i. D[]: Mảng các đỉnh. n: số đỉnh. A[][]: Ma trận kề biểu diễn quan hệ giữa các đỉnh. 1 Cấu trúc dữ liệu nêu trong bài viết này chỉ là cấu trúc dữ liệu đơn giản để cài đặt cơ bản thuật toán. Cóthể tự đề nghị cấu trúc dữ liệu thích hợp để giải quyết bài toán. 1 Tài liệu hướng dẫn thực hành Các hàm thực hiện chính Hàm khởi tạo các biến void KhoiTao(DINH D[MAX], int n) { Khởi tạo cho mỗi đỉnh i: Tính D[i].Bac D[i].MauTo = -1 D[i].MauCam[j] = 0 , j = 0 .. MAXMAU } Hàm tìm đỉnh bậc lớn nhất chưa tô int DinhBacMax(DINH D[MAX], int n) { Trả về đỉnh có bậc lớn nhất chưa tô. } Hàm tô màu 1 đỉnh void ToMau1Dinh(DINH D[MAX], int n, int i, intA[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. 2