Recursive largest first algorithm
રિકર્સિવ લાર્જેસ્ટ ફર્સ્ટ (આર. એલ. એફ.) અલ્ગોરિધમ એન. પી.-હાર્ડ ગ્રાફ રંગ સમસ્યા માટે સંશોધનાત્મક છે. તેની મૂળ દરખાસ્ત 1979માં ફ્રેન્ક લેઇટન દ્વારા કરવામાં આવી હતી. આર. એલ. એફ. અલ્ગોરિધમ દરેક રંગ વર્ગને એક સમયે એક બનાવીને આલેખના શિરોબિંદુઓને રંગો સોંપે છે. તે આલેખમાં શિરોબિંદુઓના મહત્તમ સ્વતંત્ર સમૂહને ઓળખીને, તેને સમાન રંગમાં સોંપીને અને પછી આલેખમાંથી આ શિરોબિંદુઓને દૂર કરીને આ કરે છે. આ ક્રિયાઓ બાકીના સબગ્રાફ પર પુનરાવર્તિત થાય છે જ્યાં સુધી કોઈ શિરોબિંદુ ન રહે. ઉચ્ચ ગુણવત્તાવાળા ઉકેલો (થોડા રંગોનો ઉપયોગ કરીને ઉકેલો) બનાવવા માટે, આર. એલ. એફ. અલ્ગોરિધમ "સારી ગુણવત્તાવાળા" સ્વતંત્ર સમૂહોને ઓળખવાનો પ્રયાસ કરવા માટે વિશિષ્ટ સંશોધનાત્મક નિયમોનો ઉપયોગ કરે છે. આ સંશોધનો આર. એલ. એફ. અલ્ગોરિધમને દ્વિપક્ષી, ચક્ર અને ચક્ર આલેખ માટે ચોક્કસ બનાવે છે. જો કે, સામાન્ય રીતે, અલ્ગોરિધમ અંદાજિત હોય છે અને ગ્રાફની રંગીન સંખ્યા કરતાં વધુ રંગોનો ઉપયોગ કરતા ઉકેલો સારી રીતે પરત કરી શકે છે. વર્ણન અલ્ગોરિધમને નીચેના ત્રણ પગલાઓ દ્વારા વર્ણવી શકાય છે. આ પ્રક્રિયાના અંતે, ગ્રાફના શક્ય-રંગનું પ્રતિનિધિત્વ કરતા શિરોબિંદુઓનું વિભાજન આપે છે. ચાલો એક ખાલી ઉકેલ બનીએ. ઉપરાંત, ચાલો આપણે જે ગ્રાફને રંગવા માંગીએ છીએ, તેમાં શિરોબિંદુ સમૂહ અને ધાર સમૂહનો સમાવેશ થાય છે. મહત્તમ સ્વતંત્ર સમૂહને ઓળખો. આવું કરવા માટેઃ પ્રથમ શિરોબિંદુ એ શિરોબિંદુ હોવું જોઈએ જેમાં પડોશીઓની સંખ્યા સૌથી વધુ હોય. તેમાં ઉમેરાયેલા અનુગામી શિરોબિંદુઓને તે તરીકે પસંદ કરવા જોઈએ કે જે (એ) હાલમાં કોઈપણ શિરોબિંદુને અડીને નથી, અને (બી) શિરોબિંદુઓને અડીને આવેલા પડોશીઓની મહત્તમ સંખ્યા ધરાવે છે. સ્થિતિ (બી) માં સંબંધોને ઓછામાં ઓછા પડોશીઓની સંખ્યા સાથે શિરોબિંદુ પસંદ કરીને તોડી શકાય છે. જ્યાં સુધી વધુ શિરોબિંદુઓ ઉમેરવાનું અશક્ય ન હોય ત્યાં સુધી શિરોબિંદુઓ આ રીતે ઉમેરવામાં આવે છે. હવે માંથી શિરોબિંદુઓ સુયોજિત કરો અને દૂર કરો. જો હજુ પણ શિરોબિંદુઓ હોય, તો પછી પગલું 2 પર પાછા ફરો; અન્યથા અંત. ઉદાહરણ જમણી બાજુએ બતાવેલ આલેખનો વિચાર કરો. આ એક ચક્ર આલેખ છે અને તેથી આર. એલ. એફ. દ્વારા શ્રેષ્ઠ રીતે રંગીન કરવામાં આવશે. અલ્ગોરિધમનો અમલ કરવાથી શિરોબિંદુઓ પસંદ કરવામાં આવે છે અને નીચેના ક્રમમાં રંગીન થાય છેઃ વર્ટેક્સ (રંગ 1) વર્ટેક્સ, અને પછી (રંગ 2) વર્ટેક્સ, અને પછી (રંગ 3) આ અંતિમ ત્રણ રંગનો ઉકેલ આપે છે. પ્રદર્શન આલેખમાં શિરોબિંદુઓની સંખ્યા હોવી જોઈએ અને ધારની સંખ્યા હોવી જોઈએ. મોટા ઓ નોટેશનનો ઉપયોગ કરીને, તેમના મૂળ પ્રકાશન લેઇટનમાં આરએલએફની જટિલતા હોવાનું જણાવે છે; જો કે, આમાં સુધારો કરી શકાય છે. આ અલ્ગોરિધમનો મોટાભાગનો ખર્ચ પગલું 2 ને કારણે છે, જ્યાં ઉપર જણાવેલા સંશોધનાત્મક નિયમો અનુસાર શિરોબિંદુની પસંદગી કરવામાં આવે છે. ખરેખર, દરેક વખતે જ્યારે સ્વતંત્ર સમૂહમાં ઉમેરો કરવા માટે શિરોબિંદુ પસંદ કરવામાં આવે છે, ત્યારે દરેક રંગહીન શિરોબિંદુ માટે પડોશીઓ સંબંધિત માહિતીની ફરીથી ગણતરી કરવાની જરૂર પડે છે. આ ગણતરીઓ સમયસર કરી શકાય છે, એટલે કે આર. એલ. એફ. ની એકંદર જટિલતા. જો પગલું 2 ના હ્યુરિસ્ટિક્સને રેન્ડમ પસંદગી સાથે બદલવામાં આવે, તો આ અલ્ગોરિધમનો જટિલતા ઘટાડે છે; જો કે, પરિણામી અલ્ગોરિધમનો સામાન્ય રીતે આર. એલ. એફ. ની સરખામણીમાં ઓછી ગુણવત્તાવાળા ઉકેલો આપશે. તે હવે દ્વિપક્ષી, ચક્ર અને ચક્ર આલેખ માટે પણ અચોક્કસ હશે. 2021 માં લેવિસ દ્વારા પ્રયોગમૂલક સરખામણીમાં, આર. એલ. એફ. લોભી અલ્ગોરિધમ અને રેન્ડમ ગ્રાફ પર ડીસાટુર અલ્ગોરિધમ જેવા વૈકલ્પિક હ્યુરિસ્ટિક્સ કરતાં નોંધપાત્ર રીતે વધુ સારા શિરોબિંદુ રંગનું ઉત્પાદન કરે છે. જો કે, તેની ઉચ્ચ એકંદર જટિલતાને કારણે આર. એલ. એફ. સાથે રનટાઇમ પણ આ વિકલ્પો કરતાં વધારે જોવા મળ્યો હતો. સંદર્ભો બાહ્ય કડીઓ ઉચ્ચ-પ્રદર્શન ગ્રાફ રંગ અલ્ગોરિધમ્સ સ્યુટ ઓફ ગ્રાફ કલરિંગ અલ્ગોરિધમ્સ (સી + + માં અમલમાં મૂકાયેલ) એ ગાઇડ ટુ ગ્રાફ કલરિંગઃ અલ્ગોરિધમ્સ એન્ડ એપ્લિકેશન્સ (સ્પ્રિંગર ઇન્ટરનેશનલ પબ્લિશર્સ, 2021) પુસ્તકમાં ઉપયોગમાં લેવાય છે. 1979 ઇન કમ્પ્યુટિંગ ગ્રાફ એલ્ગોરિધમ્સ ગ્રાફ કલરિંગ