Colour refinement algorithm
ग्राफ सिद्धांत और सैद्धांतिक कंप्यूटर विज्ञान में, रंग परिष्करण एल्गोरिथ्म जिसे सरल शीर्ष वर्गीकरण के रूप में भी जाना जाता है, या वेइस्फेइलर-लेमन एल्गोरिथ्म का 1-आयामी संस्करण, यह परीक्षण करने के लिए उपयोग की जाने वाली एक दिनचर्या है कि क्या दो ग्राफ समरूप हैं या नहीं। इतिहास विवरण हम शीर्ष रंगों के अनुक्रम को निम्नानुसार परिभाषित करते हैंः प्रारंभिक रंग है। यदि ग्राफ बिना लेबल वाला है, तो प्रारंभिक रंग प्रत्येक शीर्ष को एक तुच्छ रंग प्रदान करता है। यदि ग्राफ को लेबल किया गया है, तो यह शीर्ष का लेबल है। सभी शीर्षों के लिए, हम सेट करते हैं। दूसरे शब्दों में, शीर्ष का नया रंग पिछले रंग और उसके पड़ोसियों के रंगों के बहु-समूह से बना जोड़ा है। यह एल्गोरिथ्म वर्तमान रंग को परिष्कृत करता रहता है। कुछ बिंदु पर, n चरणों से पहले, जहाँ n शीर्षों की संख्या है, यह स्थिर हो जाता हैः t बढ़ने पर अब नहीं बदलता है। इस अंतिम रंग को स्थिर रंग कहा जाता है। अभिव्यक्ति यह एल्गोरिथ्म 6 लंबाई के चक्र को त्रिभुजों की एक जोड़ी से अलग नहीं करता है (उदाहरण के लिए वी. 1 इंच)। जटिलता स्थिर रंग की गणना ओ ((एन + एम) लॉग एन) में की जा सकती है जहाँ एन शीर्षों की संख्या और एम किनारों की संख्या है। यह जटिलता कुछ वर्ग के आलेखों के लिए इष्टतम साबित हुई है। संदर्भ ग्राफ एल्गोरिदम समरूपता प्रमेय