Recursive largest first algorithm
ریکرسو لارجسٹ فرسٹ (آر ایل ایف) الگورتھم این پی ہارڈ گراف کلرنگ کے مسئلے کے لیے ایک تحقیق ہے۔ اسے اصل میں 1979 میں فرینک لیٹن نے تجویز کیا تھا۔ آر ایل ایف الگورتھم ایک وقت میں ہر رنگ کی کلاس بنا کر گراف کے عمودی حصوں کو رنگ تفویض کرتا ہے۔ یہ گراف میں عمودی حصوں کے زیادہ سے زیادہ آزاد سیٹ کی شناخت کرکے، انہیں ایک ہی رنگ میں تفویض کرکے، اور پھر ان عمودی حصوں کو گراف سے ہٹا کر ایسا کرتا ہے۔ یہ حرکتیں بقیہ ذیلی گراف پر اس وقت تک دہرائی جاتی ہیں جب تک کہ کوئی عمودی نہ رہ جائے۔ اعلی معیار کے حل (چند رنگوں کا استعمال کرتے ہوئے حل) بنانے کے لیے، آر ایل ایف الگورتھم "اچھے معیار" کے آزاد سیٹوں کی شناخت کرنے کی کوشش کرنے کے لیے خصوصی ہیورسٹک قوانین کا استعمال کرتا ہے۔ یہ تحقیقات آر ایل ایف الگورتھم کو دو طرفہ، سائیکل اور وہیل گراف کے لیے درست بناتی ہیں۔ تاہم، عام طور پر، الگورتھم لگ بھگ ہے اور وہ ایسے حل واپس کر سکتا ہے جو گراف کے کرومیٹک نمبر سے زیادہ رنگ استعمال کرتے ہیں۔ تفصیل الگورتھم کو درج ذیل تین مراحل سے بیان کیا جا سکتا ہے۔ اس عمل کے اختتام پر، گراف کے قابل عمل رنگ کی نمائندگی کرنے والے عمودی حصوں کی تقسیم دیتا ہے۔ ایک خالی حل ہونے دیں۔ اس کے علاوہ، وہ گراف بننے دیں جسے ہم رنگنا چاہتے ہیں، جس میں ایک ورٹیکس سیٹ اور ایک ایج سیٹ شامل ہے۔ زیادہ سے زیادہ آزاد سیٹ کی شناخت کریں۔ ایسا کرنے کے لیے: جو پہلا ورٹیکس شامل کیا گیا ہے وہ ورٹیکس ہونا چاہیے جس میں پڑوسیوں کی سب سے زیادہ تعداد ہو۔ اس کے بعد کے عمودی حصوں کو ان کے طور پر منتخب کیا جانا چاہیے جو (a) فی الحال کسی عمودی حصے سے متصل نہیں ہیں، اور (b) پڑوسیوں کی زیادہ سے زیادہ تعداد ہے جو عمودی حصوں سے متصل ہیں۔ حالت (ب) میں بندھنوں کو کم سے کم پڑوسیوں کی تعداد کے ساتھ ورٹیکس کو منتخب کرکے توڑا جا سکتا ہے۔ عمودی حصوں کو اس طرح شامل کیا جاتا ہے جب تک کہ مزید عمودی حصوں کو شامل کرنا ناممکن نہ ہو۔ اب کے عمودی حصوں کو سیٹ کریں اور ہٹا دیں۔ اگر اب بھی عمودی ہیں، تو مرحلہ 2 پر واپس جائیں ؛ بصورت دیگر ختم کریں۔ مثال دائیں طرف دکھائے گئے گراف پر غور کریں۔ یہ ایک پہیے کا گراف ہے اور اس لیے اسے آر ایل ایف کے ذریعے بہتر رنگ دیا جائے گا۔ الگورتھم کو انجام دینے کے نتیجے میں عمودی کو منتخب کیا جاتا ہے اور مندرجہ ذیل ترتیب میں رنگ دیا جاتا ہے: ورٹیکس (رنگ 1) ورٹیکس، اور پھر (رنگ 2) ورٹیکس، اور پھر (رنگ 3) یہ حتمی تین رنگوں کا حل دیتا ہے۔ کارکردگی گراف میں عمودی حصوں کی تعداد ہونے دیں اور کناروں کی تعداد ہونے دیں۔ بگ او نوٹیشن کا استعمال کرتے ہوئے، اپنی اصل اشاعت لیٹن میں آر ایل ایف کی پیچیدگی بیان کی گئی ہے ؛ تاہم، اس میں بہتری لائی جا سکتی ہے۔ اس الگورتھم کا زیادہ تر خرچ مرحلہ 2 کی وجہ سے ہے، جہاں ورٹیکس کا انتخاب اوپر بیان کردہ ہیورسٹک قوانین کے مطابق کیا جاتا ہے۔ درحقیقت، ہر بار جب آزاد سیٹ کے اضافے کے لیے ایک ورٹیکس کا انتخاب کیا جاتا ہے، پڑوسیوں سے متعلق معلومات کو ہر غیر رنگین ورٹیکس کے لیے دوبارہ حساب کرنے کی ضرورت ہوتی ہے۔ یہ حسابات وقت پر کیے جا سکتے ہیں، یعنی کہ آر ایل ایف کی مجموعی پیچیدگی ہے۔ اگر مرحلہ 2 کے ہیورسٹکس کو بے ترتیب انتخاب سے تبدیل کیا جاتا ہے، تو اس الگورتھم کی پیچیدگی کم ہو جاتی ہے ؛ تاہم، نتیجے میں الگورتھم عام طور پر آر ایل ایف کے مقابلے میں کم معیار کے حل فراہم کرے گا۔ یہ اب دو طرفہ، سائیکل اور وہیل گراف کے لیے بھی غیر درست ہوگا۔ 2021 میں لیوس کے ایک تجرباتی موازنہ میں، آر ایل ایف کو متبادل ہیورسٹکس جیسے لالچی الگورتھم اور بے ترتیب گراف پر ڈی سیٹور الگورتھم کے مقابلے میں نمایاں طور پر بہتر ورٹیکس کلرنگ تیار کرنے کے لیے دکھایا گیا تھا۔ تاہم، آر ایل ایف کے ساتھ رن ٹائم بھی اس کی مجموعی پیچیدگی کی وجہ سے ان متبادلات سے زیادہ دیکھا گیا۔ حوالہ جات بیرونی روابط ہائی پرفارمنس گراف کلرنگ الگورتھم سوٹ آف گراف کلرنگ الگورتھم (C + + میں نافذ) کتاب A گائیڈ ٹو گراف کلرنگ: الگورتھم اینڈ ایپلی کیشنز (سپرنگر انٹرنیشنل پبلشرز، 2021) میں استعمال کیا گیا ہے۔ 1979 ان کمپیوٹنگ گراف الگورتھم گراف کلرنگ