Splittance
આલેખ સિદ્ધાંતમાં, ગણિતની એક શાખા, દિશાહીન આલેખનું વિભાજન વિભાજીત આલેખનથી તેના અંતરને માપે છે. વિભાજીત આલેખ એ એક આલેખ છે જેના શિરોબિંદુઓને સ્વતંત્ર સમૂહ (આ ઉપગણની અંદર કોઈ ધાર વિના) અને સમૂહ (આ ઉપગણની અંદર તમામ સંભવિત ધાર સાથે) માં વિભાજિત કરી શકાય છે. સ્પ્લિટન્સ એ ધાર ઉમેરાઓ અને દૂર કરવાની સૌથી નાની સંખ્યા છે જે આપેલ આલેખને વિભાજીત આલેખમાં રૂપાંતરિત કરે છે. ડિગ્રી ક્રમમાંથી ગણતરી ગ્રાફના વિભાજનની ગણતરી માત્ર ગ્રાફના ડિગ્રી ક્રમમાંથી જ કરી શકાય છે, ગ્રાફની વિગતવાર રચનાની તપાસ કર્યા વિના. ચાલો શિરોબિંદુઓ સાથેનો કોઈપણ આલેખ હોવો જોઈએ, જેની ડિગ્રી ઘટતા ક્રમમાં છે. ચાલો જેનો સૌથી મોટો સૂચકાંક બનીએ. પછી સ્પ્લિટન્સ છે આપેલ ગ્રાફ પહેલેથી જ સ્પ્લિટ ગ્રાફ છે. નહિંતર, તેને ગણતરી કરીને, મહત્તમ ડિગ્રીના શિરોબિંદુઓની જોડી વચ્ચેની તમામ ગુમ થયેલી ધારને ઉમેરીને અને બાકીના શિરોબિંદુઓની જોડી વચ્ચેની તમામ ધારને દૂર કરીને વિભાજીત આલેખમાં બનાવી શકાય છે. પરિણામે, વિભાજન અને ધાર ઉમેરાઓ અને દૂર કરવાનો ક્રમ જે તેને અનુભવે છે તે રેખીય સમયમાં ગણતરી કરી શકાય છે. એપ્લિકેશન્સ ગ્રાફના વિભાજનનો ઉપયોગ અલ્ગોરિધમ્સની કાર્યક્ષમતાને વર્ણવવા માટે પરિમાણ તરીકે પરિમાણિત જટિલતામાં કરવામાં આવ્યો છે. દાખલા તરીકે, આલેખ રંગ આ પરિમાણ હેઠળ નિશ્ચિત-પરિમાણ ટ્રેક્ટેબલ છેઃ રેખીય સમયમાં બાઉન્ડેડ સ્પ્લિટન્સના આલેખને શ્રેષ્ઠ રીતે રંગવાનું શક્ય છે. સંદર્ભો આલેખ અપરિવર્તનશીલ