Thuật toán tô màu tham lam

Trong lý thuyết đồ thị và trí tuệ nhân tạo, Thuật toán tô màu tham lam (tiếng Anh: Greedy coloring) là một trong những phương pháp tô màu cho đồ thị áp dụng giải thuật tham lam (tiếng Anh: Greedy algorithm). Thuật toán tô màu Greedy chưa phải là một thuật toán tô màu hoàn toàn chính xác. Có hai trường hợp tiêu biểu thể hiện sự chưa chính xác của thuật toán.
 Đôi khi áp dụng thuật giải này ta sẽ nhận được kết quả với số màu được tô không phải là ít nhất.
 Trên cùng một đồ thị, khi áp dụng thuật toán có thể ra các kết quả khác nhau.

Thuật toán

Tư tưởng thuật toán
Thuật toán tô màu tham lam xem xét đồ thị  với tập hợp các đỉnh  và tập các đỉnh kề . Đầu tiên ta xét các đỉnh theo thứ tự và gán cho mỗi đỉnh một màu riêng theo nguyên tắc: các đỉnh không kề với đỉnh đang xét (không có cạnh nối trực tiếp) thì được phép tô cùng một màu, cấm tô màu đó cho các đỉnh có cạnh kề với đỉnh đang xét. Thuật toán lặp lại cho đến khi tất cả các đỉnh được tô màu.

Mã giả
SET .

SET .

FOR .

{
Tô màu k > 0 cho đỉnh vj khác với đỉnh kề nó

 MIN  AND 

} Lặp lại đến tô màu xong.

Minh họa thuật giải

Xem thêm
 lý thuyết đồ thị
 trí tuệ nhân tạo
 giải thuật tham lam

Tham khảo
. As cited by .
.
. As cited by .
.
. As cited by .
.
.
.
.
.
.
.
.

Lý thuyết đồ thị
Trí tuệ nhân tạo
Tô màu đồ thị