Colour refinement algorithm
આલેખ સિદ્ધાંત અને સૈદ્ધાંતિક કોમ્પ્યુટર વિજ્ઞાનમાં, રંગ શુદ્ધિકરણ અલ્ગોરિધમ, જેને નિષ્કપટ શિરોબિંદુ વર્ગીકરણ તરીકે પણ ઓળખવામાં આવે છે, અથવા વેઇસ્ફેઇલર-લેમન અલ્ગોરિધમનું 1-પરિમાણીય સંસ્કરણ, એ બે આલેખ સમરૂપ છે કે નહીં તે ચકાસવા માટે વપરાય છે. ઇતિહાસ વર્ણન આપણે શિરોબિંદુ રંગોના ક્રમને નીચે પ્રમાણે વ્યાખ્યાયિત કરીએ છીએઃ તે પ્રારંભિક રંગ છે. જો આલેખ લેબલ વગરનો હોય, તો પ્રારંભિક રંગ દરેક શિરોબિંદુને તુચ્છ રંગ સોંપે છે. જો આલેખ લેબલ થયેલ હોય, તો તે શિરોબિંદુનું લેબલ છે. બધા શિરોબિંદુઓ માટે, આપણે સુયોજિત કરીએ છીએ. બીજા શબ્દોમાં કહીએ તો, શિરોબિંદુનો નવો રંગ એ અગાઉના રંગ અને તેના પડોશીઓના રંગોના બહુવિધ સમૂહમાંથી રચાયેલી જોડી છે. આ અલ્ગોરિધમ વર્તમાન રંગને શુદ્ધ કરતું રહે છે. અમુક સમયે, n પગલાંઓ પહેલાં, જ્યાં n એ શિરોબિંદુઓની સંખ્યા છે, તે સ્થિર થાય છેઃ જ્યારે t વધે છે ત્યારે તે હવે બદલાતું નથી. આ અંતિમ રંગને સ્થિર રંગ કહેવામાં આવે છે. અભિવ્યક્તિ આ અલ્ગોરિધમ 6 લંબાઈના ચક્રને ત્રિકોણની જોડીથી અલગ પાડતું નથી (ઉદાહરણ તરીકે V. 1 in). જટિલતા સ્થિર રંગની ગણતરી ઓ ((એન + એમ) લોગ એન) માં કરી શકાય છે જ્યાં એન એ શિરોબિંદુઓની સંખ્યા છે અને એમ એ ધારની સંખ્યા છે. આ જટિલતા આલેખના અમુક વર્ગ માટે શ્રેષ્ઠ સાબિત થઈ છે. સંદર્ભો ગ્રાફ અલ્ગોરિધમ્સ આઇસોમોર્ફિઝમ પ્રમેયો