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 BULLET Đô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 BULLET 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ị formula _ 1 với tập_hợp các đỉnh formula _ 2 và tập các đỉnh kề formula _ 3 Đầ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 formula _ 4 SET formula _ 5 FOR formula _ 6 Tô màu k 0 cho đỉnh vj khác với đỉnh kề nó formula _ 7 MIN formula _ 8 AND formula _ 9 Lặp lại đến tô màu xong Xem thêm BULLET lý_thuyết đồ_thị BULLET trí_tuệ_nhân_tạo BULLET giải_thuật tham_lam Tham_khảo BULLET As cited by BULLET As cited by BULLET As cited by BULLET BULLET BULLET BULLET
Thuật_toán tô màu tham_lam