Colour refinement algorithm
گراف تھیوری اور نظریاتی کمپیوٹر سائنس میں، رنگین ریفائنمنٹ الگورتھم جسے نییو ورٹیکس کی درجہ بندی بھی کہا جاتا ہے، یا ویسفیلر-لیمن الگورتھم کا 1 جہتی ورژن، یہ جانچنے کے لیے استعمال ہونے والا معمول ہے کہ آیا دو گراف آئسومورفک ہیں یا نہیں۔ تاریخ کی تفصیل ہم عمودی رنگوں کی ایک ترتیب کی وضاحت کرتے ہیں جس کی وضاحت مندرجہ ذیل ہے: ابتدائی رنگ ہے۔ اگر گراف غیر لیبل شدہ ہے، تو ابتدائی رنگ ہر سرے کو ایک معمولی رنگ تفویض کرتا ہے۔ اگر گراف کو لیبل کیا گیا ہے، تو یہ ورٹیکس کا لیبل ہے۔ تمام عمودی کے لیے، ہم سیٹ کرتے ہیں۔ دوسرے لفظوں میں، ورٹیکس کا نیا رنگ پچھلے رنگ اور اس کے پڑوسیوں کے رنگوں کے ملٹی سیٹ سے بنا جوڑا ہے۔ یہ الگورتھم موجودہ رنگ کو بہتر بناتا رہتا ہے۔ کسی وقت، n مراحل سے پہلے، جہاں n چوٹیوں کی تعداد ہے، یہ مستحکم ہوتا ہے: جب t بڑھتا ہے تو اب تبدیل نہیں ہوتا ہے۔ اس آخری رنگ کو مستحکم رنگ کہا جاتا ہے۔ اظہاریت یہ الگورتھم 6 لمبائی کے چکر کو مثلث کے جوڑے سے ممتاز نہیں کرتا ہے (مثال کے طور پر V. 1 in)۔ پیچیدگی مستحکم رنگ O ((n + m) لاگ n) میں قابل حساب ہے جہاں n عمودی کی تعداد اور m کناروں کی تعداد ہے۔ یہ پیچیدگی گراف کے کچھ طبقے کے لیے بہترین ثابت ہوئی ہے۔ حوالہ جات گراف الگورتھم آئسومورفزم تھیوریمز