Colour refinement algorithm
வரைபடக் கோட்பாடு மற்றும் கோட்பாட்டு கணினி அறிவியலில், வண்ணச் சுத்திகரிப்பு வழிமுறை, அப்பாவித்தனமான வெர்டெக்ஸ் வகைப்பாடு என்றும் அழைக்கப்படுகிறது, அல்லது வெயிஸ்ஃபீலர்-லெமான் வழிமுறையின் 1 பரிமாண பதிப்பு, இரண்டு வரைபடங்கள் ஐசோமார்பிக் அல்லது இல்லையா என்பதைச் சோதிக்கப் பயன்படுத்தப்படும் ஒரு வழக்கமாகும். வரலாறு விளக்கம் பின்வருமாறு வரையறுக்கப்பட்ட உச்சி வண்ணங்களின் வரிசையை நாம் வரையறுக்கிறோம்ஃ இது ஆரம்ப நிறமாகும். வரைபடம் பெயரிடப்படாவிட்டால், ஆரம்ப வண்ணமயமாக்கல் ஒவ்வொரு உச்சிக்கும் ஒரு அற்பமான நிறத்தை ஒதுக்குகிறது. வரைபடம் பெயரிடப்பட்டிருந்தால், அது உச்சியின் முத்திரையாகும். அனைத்து செங்குத்துகளுக்கும், நாம் அமைக்கிறோம். வேறு வார்த்தைகளில் கூறுவதானால், உச்சியின் புதிய நிறம் முந்தைய நிறத்திலிருந்து உருவான ஜோடி மற்றும் அதன் அண்டை நாடுகளின் வண்ணங்களின் மல்டிசெட் ஆகும். இந்த வழிமுறை தற்போதைய வண்ணமயமாக்கலைச் செம்மைப்படுத்துகிறது. ஒரு கட்டத்தில், n படிகளுக்கு முன், n என்பது செங்குத்துகளின் எண்ணிக்கை, இது உறுதிப்படுத்துகிறதுஃ t அதிகரிக்கும் போது இனி மாறாது. இந்த இறுதி நிறம் நிலையான நிறம் என்று அழைக்கப்படுகிறது. வெளிப்பாடு இந்த வழிமுறை 6 நீளம் கொண்ட ஒரு சுழற்சியை ஒரு ஜோடி முக்கோணங்களிலிருந்து வேறுபடுத்துவதில்லை (எடுத்துக்காட்டாக வி. 1 இன்). சிக்கலானது நிலையான நிறம் O ((n + m) பதிவு n) இல் கணக்கிடப்படுகிறது, இதில் n என்பது செங்குத்துகளின் எண்ணிக்கை மற்றும் m என்பது விளிம்புகளின் எண்ணிக்கை. இந்த சிக்கலானது சில வகை வரைபடங்களுக்கு உகந்ததாக நிரூபிக்கப்பட்டுள்ளது. குறிப்புகள் வரைபட வழிமுறைகள் ஐசோமார்பிசம் கோட்பாடுகள்