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ị $G(V)$ với tập hợp các đỉnh $V=[v_1,\mathrm{...},v_n]$ và tập các đỉnh kề $A_{v_j}$. Đầ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 $c(v_j)\leftarrow 0\mathrm{\forall }1\le j\le n$.

SET $c(v_1)\leftarrow 1$.

FOR $2\le j\le n$.

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

$c(v_j)\leftarrow$ MIN $(k\in \mathrm{Z}\Vert k>0$ AND $c(\omega )\ne k\mathrm{\forall }\omega \in A_{v_j})$

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

Minh họa thuật giải

• Tô màu đỉnh 1
  Tô màu đỉnh 1
• Tô màu đỉnh 2
  Tô màu đỉnh 2
• Tô màu đỉnh 3
  Tô màu đỉnh 3
• Tô màu đỉnh 4
  Tô màu đỉnh 4
• Tô màu đỉnh 5
  Tô màu đỉnh 5

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 .
• .
• .
• .
• .
• .
• .
• .
• .