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

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Trong lý thuyết đồ thị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[sửa | sửa mã nguồn]

Tư tưởng thuật toán[sửa | sửa mã nguồ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 đanh 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ả[sửa | sửa mã nguồn]

SET c(v_j)\leftarrow 0 \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 \Zeta\|k>0 AND c(\omega)\ne k  \forall \omega \in A_{v_j})

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

Minh họa thuật giải[sửa | sửa mã nguồn]

Xem thêm[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]

  • Chvátal, Václav (1984), “Perfectly orderable graphs”, trong Berge, Claude; Chvátal, Václav, 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., 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 .