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