Colour refinement algorithm
গ্রাফ তত্ত্ব এবং তাত্ত্বিক কম্পিউটার বিজ্ঞানে, রঙ পরিশোধন অ্যালগরিদম যা নিষ্ক্রিয় ভার্টেক্স শ্রেণিবিন্যাস বা ওয়েইসফেলার-লেম্যান অ্যালগরিদমের 1-মাত্রিক সংস্করণ নামেও পরিচিত, দুটি গ্রাফ সমতুল্য কিনা তা পরীক্ষা করার জন্য ব্যবহৃত একটি রুটিন। ইতিহাসের বিবরণ আমরা নিম্নরূপ সংজ্ঞায়িত শীর্ষ রঙগুলির একটি ক্রমকে সংজ্ঞায়িত করিঃ এটি প্রাথমিক রঙ। যদি গ্রাফটি লেবেলবিহীন হয়, তবে প্রাথমিক রঙ প্রতিটি শীর্ষে একটি তুচ্ছ রঙ বরাদ্দ করে। যদি গ্রাফটি লেবেলযুক্ত হয়, তবে এটি শীর্ষের লেবেল। সমস্ত শীর্ষের জন্য, আমরা সেট করি। অন্য কথায়, শীর্ষের নতুন রঙ হল পূর্ববর্তী রঙ এবং তার প্রতিবেশীদের রঙের মাল্টিসেট থেকে গঠিত জোড়া। এই অ্যালগরিদম বর্তমান রঙকে পরিমার্জন করে। কিছু সময়ে, n ধাপের আগে, যেখানে n হল শীর্ষের সংখ্যা, এটি স্থিতিশীল হয়ঃ t বাড়লে আর পরিবর্তিত হয় না। এই চূড়ান্ত রঙকে স্থিতিশীল রঙ বলা হয়। অভিব্যক্তি এই অ্যালগরিদম 6 দৈর্ঘ্যের একটি চক্রকে এক জোড়া ত্রিভুজ থেকে আলাদা করে না (উদাহরণস্বরূপ V. 1 ইঞ্চি)। জটিলতা স্থিতিশীল রঙ O ((n + m) লগ n)-এ গণনাযোগ্য যেখানে n হল শীর্ষের সংখ্যা এবং m হল প্রান্তের সংখ্যা। এই জটিলতা কিছু শ্রেণীর গ্রাফের জন্য সর্বোত্তম বলে প্রমাণিত হয়েছে। রেফারেন্স গ্রাফ অ্যালগরিদম আইসোমরফিজম উপপাদ্য