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},...,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\forall 1\leq j\leq n$.

SET $c(v_{1})\leftarrow 1$.

FOR $2\leq j\leq 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} \|k>0$ AND $c(\omega )\neq k\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 2
• 
  Tô màu đỉnh 3
• 
  Tô màu đỉnh 4
• 
  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

• Chvátal, Václav (1984), “Perfectly orderable graphs”, trong Berge, Claude; Chvátal, Václav (biên tập), Topics in Perfect Graphs, Annals of Discrete Mathematics, 21, Amsterdam: North-Holland, tr. 63–68. As cited by Maffray (2003).
• Irani, Sandy (1994), “Coloring inductive graphs on-line”, Algorithmica, 11 (1): 53–72, doi:10.1007/BF01294263.
• Kierstead, H. A.; Trotter, W. A. (1981), “An extremal problem in recursive combinatorics”, Congress. Numer., 33: 143–153. As cited by Irani (1994).
• Kučera, Luděk (1991), “The greedy coloring is a bad probabilistic algorithm”, Journal of Algorithms, 12 (4): 674–684, doi:10.1016/0196-6774(91)90040-6.
• Johnson, D. S. (1979), “Worst case behavior of graph coloring algorithms”, Proc. 5th Southeastern Conf. Combinatorics, Graph Theory and Computation, Winnipeg: Utilitas Mathematica, tr. 513–527. As cited by Maffray (2003).
• Lovász, L. (1975), “Three short proofs in graph theory”, Journal of Combinatorial Theory, Series B, 19 (3): 269–271, doi:10.1016/0095-8956(75)90089-1.
• Lovász, L.; Saks, M. E.; Trotter, W. A. (1989), “An on-line graph coloring algorithm with sublinear performance ratio”, Discrete Mathematics, 75 (1–3): 319–325, doi:10.1016/0012-365X(89)90096-4.
• Maffray, Frédéric (2003), “On the coloration of perfect graphs”, trong Reed, Bruce A.; Sales, Cláudia L. (biên tập), Recent Advances in Algorithms and Combinatorics, CMS Books in Mathematics, 11, Springer-Verlag, tr. 65–84, doi:10.1007/0-387-22444-0_3, ISBN 0-387-95434-1.
• Middendorf, Matthias; Pfeiffer, Frank (1990), “On the complexity of recognizing perfectly orderable graphs”, Discrete Mathematics, 80 (3): 327–333, doi:10.1016/0012-365X(90)90251-C.
• Sysło, Maciej M. (1989), “Sequential coloring versus Welsh-Powell bound”, Discrete Mathematics, 74 (1–2): 241–243, doi:10.1016/0012-365X(89)90212-4.
• Vishwanathan, S. (1990), “Randomized online graph coloring”, Proc. 31st IEEE Symp. Foundations of Computer Science (FOCS '90), 2, tr. 464–469, doi:10.1109/FSCS.1990.89567, ISBN 0-8186-2082-X.
• Welsh, D. J. A.; Powell, M. B. (1967), “An upper bound for the chromatic number of a graph and its application to timetabling problems”, The Computer Journal, 10 (1): 85–86, doi:10.1093/comjnl/10.1.85.
• Zaker, Manouchehr (2006), “Results on the Grundy chromatic number of graphs”, Discrete Mathematics, 306 (2–3): 3166–3173, doi:10.1016/j.disc.2005.06.044.