Recursive largest first algorithm
रिकर्सिव लार्जेस्ट फर्स्ट (आर. एल. एफ.) एल्गोरिथ्म एन. पी.-हार्ड ग्राफ रंग समस्या के लिए एक शोधात्मक है। यह मूल रूप से 1979 में फ्रैंक लीटन द्वारा प्रस्तावित किया गया था। आर. एल. एफ. एल्गोरिदम एक समय में प्रत्येक रंग वर्ग का निर्माण करके ग्राफ के शीर्षों को रंग प्रदान करता है। यह ग्राफ में शीर्षों के एक अधिकतम स्वतंत्र सेट की पहचान करके, इन्हें एक ही रंग में निर्दिष्ट करके, और फिर ग्राफ से इन शीर्षों को हटाकर ऐसा करता है। इन क्रियाओं को शेष उपग्राफ पर तब तक दोहराया जाता है जब तक कि कोई शीर्ष न रह जाए। उच्च गुणवत्ता वाले समाधान (कुछ रंगों का उपयोग करके समाधान) बनाने के लिए, आर. एल. एफ. एल्गोरिदम "अच्छी गुणवत्ता" वाले स्वतंत्र सेटों की पहचान करने का प्रयास करने के लिए विशेष शोध नियमों का उपयोग करता है। ये शोध आर. एल. एफ. एल्गोरिदम को द्विदलीय, चक्र और चक्र ग्राफ के लिए सटीक बनाते हैं। सामान्य तौर पर, हालांकि, एल्गोरिथ्म अनुमानित है और अच्छी तरह से उन समाधानों को वापस कर सकता है जो ग्राफ की रंगीन संख्या की तुलना में अधिक रंगों का उपयोग करते हैं। एल्गोरिदम को निम्नलिखित तीन चरणों द्वारा वर्णित किया जा सकता है। इस प्रक्रिया के अंत में, ग्राफ के एक व्यवहार्य रंग का प्रतिनिधित्व करने वाले शीर्षों का एक विभाजन देता है। एक खाली समाधान होने दें। इसके अलावा, हम जिस ग्राफ को रंगना चाहते हैं, उसमें एक वर्टेक्स सेट और एक एज सेट शामिल है। एक अधिकतम स्वतंत्र समुच्चय की पहचान करें। ऐसा करने के लिएः जोड़ा गया पहला शीर्ष वह शीर्ष होना चाहिए जिसमें पड़ोसियों की संख्या सबसे अधिक हो। बाद में जोड़े गए शीर्षों को उन के रूप में चुना जाना चाहिए जो (ए) वर्तमान में किसी भी शीर्ष से सटे नहीं हैं, और (बी) पड़ोसियों की अधिकतम संख्या है जो शीर्षों से सटे हैं। स्थिति (बी) में संबंधों को पड़ोसियों की न्यूनतम संख्या के साथ शीर्ष का चयन करके तोड़ा जा सकता है। वर्टीस को इस तरह से तब तक जोड़ा जाता है जब तक कि आगे वर्टीस को जोड़ना असंभव न हो। अब से के शीर्षों को सेट करें और हटा दें। यदि अभी भी शीर्ष हैं, तो चरण 2 पर लौटें; अन्यथा समाप्त करें। उदाहरण दाईं ओर दिखाए गए ग्राफ पर विचार करें। यह एक चक्र ग्राफ है और इसलिए आर. एल. एफ. द्वारा इष्टतम रूप से रंगीन किया जाएगा। एल्गोरिदम को निष्पादित करने के परिणामस्वरूप शीर्षों का चयन किया जाता है और निम्नलिखित क्रम में रंग दिया जाता हैः वर्टेक्स (रंग 1) वर्टेक्स, और फिर (रंग 2) वर्टेक्स, और फिर (रंग 3) यह अंतिम तीन रंग का समाधान देता है। प्रदर्शन ग्राफ में शीर्षों की संख्या होने दें और किनारों की संख्या होने दें। बिग ओ संकेतन का उपयोग करते हुए, अपने मूल प्रकाशन लाइटन में आरएलएफ की जटिलता को बताया गया है; हालाँकि, इसमें सुधार किया जा सकता है। इस एल्गोरिथ्म का अधिकांश खर्च चरण 2 के कारण होता है, जहां शीर्ष चयन ऊपर बताए गए शोध नियमों के अनुसार किया जाता है। वास्तव में, हर बार जब स्वतंत्र समूह के अतिरिक्त के लिए एक शीर्ष का चयन किया जाता है, तो प्रत्येक रंगहीन शीर्ष के लिए पड़ोसियों के बारे में जानकारी की पुनः गणना करने की आवश्यकता होती है। ये गणनाएँ समय पर की जा सकती हैं, जिसका अर्थ है कि आर. एल. एफ. की समग्र जटिलता है। यदि चरण 2 के शोध को यादृच्छिक चयन से बदल दिया जाता है, तो इस एल्गोरिथ्म की जटिलता कम हो जाती है; हालाँकि, परिणामी एल्गोरिथ्म आमतौर पर आर. एल. एफ. की तुलना में कम गुणवत्ता वाले समाधान प्रदान करेगा। यह अब द्विदलीय, चक्र और चक्र ग्राफ के लिए भी सटीक नहीं होगा। 2021 में लुईस द्वारा एक अनुभवजन्य तुलना में, आर. एल. एफ. को लालची एल्गोरिदम और यादृच्छिक ग्राफ पर डीसैटुर एल्गोरिदम जैसे वैकल्पिक शोध की तुलना में काफी बेहतर शीर्ष रंगों का उत्पादन करने के लिए दिखाया गया था। हालाँकि, आर. एल. एफ. के साथ रनटाइम भी अपनी उच्च समग्र जटिलता के कारण इन विकल्पों की तुलना में अधिक देखा गया। ए गाइड टू ग्राफ कलरिंगः एल्गोरिदम एंड एप्लीकेशन (स्प्रिंगर इंटरनेशनल पब्लिशर्स, 2021) पुस्तक में उपयोग किए गए उच्च-प्रदर्शन ग्राफ कलरिंग एल्गोरिदम सूट ऑफ ग्राफ कलरिंग एल्गोरिदम (सी + + में लागू)। 1979 कंप्यूटिंग ग्राफ एल्गोरिदम ग्राफ रंग में