Maximum cut
આલેખ માટે, મહત્તમ કટ એ એક કટ છે જેનું કદ ઓછામાં ઓછું અન્ય કોઈપણ કટ જેટલું હોય છે. એટલે કે, તે આલેખના શિરોબિંદુઓનું બે પૂરક સમૂહોમાં વિભાજન છે અને, જેમ કે અને વચ્ચેની ધારની સંખ્યા શક્ય તેટલી મોટી હોય છે. આવી કટ શોધવી એ મહત્તમ કટ સમસ્યા તરીકે ઓળખાય છે. સમસ્યાને નીચે પ્રમાણે સરળ રીતે વર્ણવી શકાય છે. કોઈ વ્યક્તિ શિરોબિંદુ સમૂહનો ઉપગણ એવો ઇચ્છે છે કે તેની વચ્ચેની ધારની સંખ્યા અને પૂરક ઉપગણ શક્ય તેટલી મોટી હોય. તેવી જ રીતે, શક્ય તેટલી ધાર સાથે ગ્રાફનો દ્વિપક્ષી સબગ્રાફ જોઈએ છે. વેઇટેડ મેક્સ-કટ નામની સમસ્યાનું વધુ સામાન્ય સંસ્કરણ છે, જ્યાં દરેક ધાર વાસ્તવિક સંખ્યા, તેના વજન સાથે સંકળાયેલી હોય છે, અને તેનો ઉદ્દેશ કિનારીઓની સંખ્યાને બદલે તેની અને તેના પૂરક વચ્ચેની કિનારીઓનું કુલ વજન વધારવાનો છે. હકારાત્મક અને નકારાત્મક બંને વજનને મંજૂરી આપતી ભારિત મહત્તમ-કટ સમસ્યાને તમામ વજનમાં નિશાનીને પલટી મારીને તુચ્છ રીતે ભારિત લઘુત્તમ કટ સમસ્યામાં રૂપાંતરિત કરી શકાય છે. નીચલી સીમાઓ એડવર્ડ્સે શિરોબિંદુઓ અને ધારવાળા આલેખ પર મેક્સ-કટ માટે નીચેની બે નીચલી સીમા મેળવી હતી ((a) મનસ્વી છે, પરંતુ (b) તે જોડાયેલ છે): (a) (b) બાઉન્ડ (b) ને ઘણીવાર એડવર્ડ્સ-એર્ડોસ બાઉન્ડ કહેવામાં આવે છે કારણ કે એર્ડસે તેને અનુમાન લગાવ્યું હતું. એડવર્ડ્સે એડવર્ડ્સ-એર્ડોસને સંભવિત પદ્ધતિનો ઉપયોગ કરીને બંધાયેલા સાબિત કર્યા; ક્રોસ્ટન એટ અલ. રેખીય બીજગણિત અને સ્યુડો-બુલિયન કાર્યોના વિશ્લેષણનો ઉપયોગ કરીને બાઉન્ડ સાબિત કર્યું. ક્રોસ્ટન એટ અલનો પુરાવો. આપણને એડવર્ડ્સ-એર્ડોસને હસ્તાક્ષરિત આલેખ પર બેલેન્સ્ડ સબગ્રાફ પ્રોબ્લેમ (બી. એસ. પી.) સાથે જોડવાની મંજૂરી આપે છે, એટલે કે. આલેખ જ્યાં દરેક ધાર + અથવા-સોંપવામાં આવે છે. ઉપગણમાં વિભાજન માટે અને, ધાર સંતુલિત હોય છે જો અને અને એક જ ઉપગણમાં હોય, અથવા અને અને અલગ ઉપગણ હોય. બી. એસ. પી. નો ઉદ્દેશ સંતુલિત ધારની મહત્તમ સંખ્યા સાથે પાર્ટીશન શોધવાનો છે. એડવર્ડ્સ-એર્ડોસ દરેક જોડાયેલા હસ્તાક્ષરિત આલેખ માટે નીચલી સીમા આપે છે. આલેખના વિશેષ વર્ગો માટે બાઉન્ડ (એ) માં સુધારો કરવામાં આવ્યો હતોઃ ત્રિકોણ-મુક્ત આલેખ, આપેલ મહત્તમ ડિગ્રીના આલેખ,-મુક્ત આલેખ, વગેરે, જુઓ દા. ત. પોલજાક અને તુર્ઝિકે એડવર્ડ્સ-એર્ડોસને ભારિત મેક્સ-કટ સુધી લંબાવ્યોઃ તેનું વજન ક્યાં અને ક્યાં છે અને તેનું લઘુતમ વજન ફેલાયેલું વૃક્ષ. તાજેતરમાં, ગુતિન અને યેઓએ ભારિત આલેખના વિશેષ વર્ગો માટે મનસ્વી ભારિત આલેખ અને સીમાઓ માટે બંધાયેલા પોલજાક-તુર્ઝિકને વિસ્તૃત કરતા ભારિત મેક્સ-કટ માટે સંખ્યાબંધ નીચલી સીમાઓ મેળવી હતી. કોમ્પ્યુટેશનલ જટિલતા મહત્તમ કાપને લગતી નીચેની નિર્ણય સમસ્યાનો સૈદ્ધાંતિક કોમ્પ્યુટર વિજ્ઞાનમાં વ્યાપક અભ્યાસ કરવામાં આવ્યો છેઃ આલેખ G અને પૂર્ણાંક k આપવામાં આવે તો, નક્કી કરો કે G માં ઓછામાં ઓછો k કદનો કાપ છે કે કેમ. આ સમસ્યા NP-પૂર્ણ તરીકે ઓળખાય છે. તે જોવાનું સરળ છે કે સમસ્યા એન. પી. માં છેઃ હા જવાબ પૂરતો મોટો કટ રજૂ કરીને સાબિત કરવો સરળ છે. સમસ્યાની એન. પી.-પૂર્ણતા દર્શાવી શકાય છે, ઉદાહરણ તરીકે, મહત્તમ 2-સંતોષકારકતામાં ઘટાડો (મહત્તમ સંતોષકારક સમસ્યાનું પ્રતિબંધ). નિર્ણય સમસ્યાનું ભારિત સંસ્કરણ કાર્પની 21 એન. પી.-પૂર્ણ સમસ્યાઓમાંની એક હતી; કાર્પે પાર્ટીશન સમસ્યામાંથી ઘટાડો કરીને એન. પી.-પૂર્ણતા દર્શાવી હતી. ઉપરોક્ત નિર્ણય સમસ્યાના કેનોનિકલ ઓપ્ટિમાઇઝેશન પ્રકારને સામાન્ય રીતે મેક્સિમમ-કટ પ્રોબ્લેમ અથવા મેક્સિમમ-કટ તરીકે ઓળખવામાં આવે છે અને તેને આ રીતે વ્યાખ્યાયિત કરવામાં આવે છેઃ ગ્રાફ G આપવામાં આવે તો, મેક્સિમમ કટ શોધો. ઓપ્ટિમાઇઝેશન વેરિઅન્ટ એનપી-હાર્ડ તરીકે ઓળખાય છે. તેનાથી વિપરીત સમસ્યા, લઘુતમ કાપ શોધવાની સમસ્યા ફોર્ડ-ફુલ્કરસન અલ્ગોરિધમ દ્વારા અસરકારક રીતે ઉકેલી શકાય તેવી હોવાનું જાણીતું છે. એલ્ગોરિધમ્સ બહુપદી-સમય અલ્ગોરિધમ્સ જેમ કે મહત્તમ-કટ સમસ્યા એન. પી.-સખત છે, સામાન્ય આલેખમાં મહત્તમ-કટ માટે કોઈ બહુપદી-સમય અલ્ગોરિધમ્સ જાણીતા નથી. જો કે, સમતલીય આલેખમાં, મહત્તમ-કાપ સમસ્યા માર્ગ નિરીક્ષણ સમસ્યા માટે બેવડી છે (ટૂંકી મુલાકાત કે જે ઓછામાં ઓછી એક વાર આલેખની દરેક ધારની મુલાકાત લે છે તે શોધવાની સમસ્યા), એ અર્થમાં કે જે કિનારીઓ ગ્રાફ G ના મહત્તમ કટ-સેટ સાથે સંબંધિત નથી તે કિનારીઓની દ્વિગુણિત છે જે G ના બેવડા આલેખના શ્રેષ્ઠ નિરીક્ષણ પ્રવાસમાં બમણી થાય છે. શ્રેષ્ઠ નિરીક્ષણ પ્રવાસ એક સ્વ-વિચ્છેદન વળાંક બનાવે છે જે સમતલને બે ઉપગણમાં અલગ કરે છે, બિંદુઓનો ઉપગણ કે જેના માટે વળાંકની સંખ્યા સમાન હોય છે અને ઉપગણ કે જેના માટે વળાંકની સંખ્યા વિચિત્ર હોય છે; આ બે ઉપગણ એક કટ બનાવે છે જેમાં તમામ કિનારીઓનો સમાવેશ થાય છે જેની દ્વિગુણિત દેખાય છે. માર્ગ નિરીક્ષણ સમસ્યાને બહુપદી સમયમાં ઉકેલી શકાય છે, અને આ દ્વૈતતા સમતલીય આલેખ માટે બહુપદી સમયમાં મહત્તમ કટ સમસ્યાને પણ હલ કરવાની મંજૂરી આપે છે. મહત્તમ-વિભાજન સમસ્યા જોકે એન. પી.-હાર્ડ તરીકે ઓળખાય છે. મહત્તમ-કટ સમસ્યા એ એ. પી. એક્સ.-હાર્ડ છે, જેનો અર્થ છે કે જ્યાં સુધી પી = એન. પી. ન હોય ત્યાં સુધી તેના માટે કોઈ બહુપદી-સમય અંદાજ યોજના (પી. ટી. એ. એસ.) નથી, જે આપખુદ રીતે શ્રેષ્ઠ ઉકેલની નજીક છે. આમ, દરેક જાણીતા બહુપદી-સમય અંદાજ અલ્ગોરિધમ એક કરતાં સખત રીતે ઓછો અંદાજ ગુણોત્તર પ્રાપ્ત કરે છે. એક સરળ રેન્ડમાઇઝ્ડ 0.5-approximation અલ્ગોરિધમ છેઃ દરેક શિરોબિંદુ માટે એક સિક્કાને પલટી મારીને નક્કી કરો કે તેને કયા અડધા પાર્ટીશનને સોંપવો. અપેક્ષા મુજબ, અડધી ધાર કાપવામાં આવે છે. આ અલ્ગોરિધમને શરતી સંભાવનાઓની પદ્ધતિથી અલગ કરી શકાય છે; તેથી એક સરળ નિર્ધારક બહુપદી-સમય 0.5-approximation અલ્ગોરિધમ પણ છે. આવા એક અલ્ગોરિધમ આપેલ આલેખના શિરોબિંદુઓના મનસ્વી પાર્ટીશનથી શરૂ થાય છે અને વારંવાર પાર્ટીશનની એક બાજુથી બીજી બાજુ એક સમયે એક શિરોબિંદુને ખસેડે છે, દરેક તબક્કે ઉકેલમાં સુધારો કરે છે, જ્યાં સુધી આ પ્રકારના કોઈ વધુ સુધારા કરી શકાતા નથી. પુનરાવર્તનોની સંખ્યા સૌથી વધુ છે કારણ કે અલ્ગોરિધમ દરેક પગલામાં ઓછામાં ઓછી એક ધાર દ્વારા કટને સુધારે છે. જ્યારે અલ્ગોરિધમ સમાપ્ત થાય છે, ત્યારે દરેક શિરોબિંદુની ઓછામાં ઓછી અડધી ધાર કટની હોય છે, કારણ કે અન્યથા શિરોબિંદુને ખસેડવાથી કટમાં સુધારો થશે. તેથી, કટમાં ઓછામાં ઓછી ધારનો સમાવેશ થાય છે. શ્રેષ્ઠ જાણીતા અંદાજ ગુણોત્તર સાથે મેક્સ-કટ માટે બહુપદી-સમય અંદાજ અલ્ગોરિધમ ગોમેન્સ અને વિલિયમસન દ્વારા અર્ધ-અનંત પ્રોગ્રામિંગ અને રેન્ડમાઇઝ્ડ રાઉન્ડિંગનો ઉપયોગ કરીને એક પદ્ધતિ છે જે અંદાજ ગુણોત્તર પ્રાપ્ત કરે છે જ્યાં જો અનન્ય રમત અનુમાન સાચું હોય, તો મહત્તમ કટ માટે આ શ્રેષ્ઠ સંભવિત અંદાજ ગુણોત્તર છે. આવી અપ્રમાણિત ધારણાઓ વિના, તેના કરતા વધુ સારા અંદાજ ગુણોત્તર સાથે મહત્તમ-કટ મૂલ્યનો અંદાજ લગાવવો એન. પી.-હાર્ડ સાબિત થયું છે. તેમાં ઓપન-સોર્સ અમલીકરણ સહિત આ સમસ્યા માટે 10 હ્યુરિસ્ટિક્સનું વિસ્તૃત વિશ્લેષણ છે. પરિમાણિત અલ્ગોરિધમ્સ અને કર્નલાઇઝેશન જ્યારે તે સાબિત કરવું તુચ્છ છે કે ઓછામાં ઓછું કદ (પરિમાણ) k નો કટ શોધવાની સમસ્યા ફિક્સ્ડ-પેરામીટર ટ્રેક્ટેબલ (FPT) છે, તે નક્કી કરવાની સમસ્યા માટે ફિક્સ્ડ-પેરામીટર ટ્રેક્ટેબિલિટી બતાવવી ખૂબ મુશ્કેલ છે કે શું ગ્રાફ G માં ઓછામાં ઓછા એડવર્ડ્સ-એર્ડોસ લોઅર બાઉન્ડ (ઉપરની લોઅર બાઉન્ડ્સ જુઓ) વત્તા (પરિમાણ) k. ક્રોસ્ટન એટ અલ. સાબિત કર્યું કે સમસ્યાને સમયસર ઉકેલી શકાય છે અને કદના કર્નલને સ્વીકારે છે. ક્રોસ્ટન એટ અલ. બેલેન્સ્ડ સબગ્રાફ પ્રોબ્લેમ (બી. એસ. પી., ઉપરની લોઅર બાઉન્ડ્સ જુઓ) માટે ફિક્સ્ડ-પેરામીટર ટ્રેક્ટેબિલિટી પરિણામને વિસ્તૃત કર્યું અને કર્નલનું કદ સુધારીને (બી. એસ. પી. માટે પણ ધરાવે છે) કર્યું. Etscheid અને Mnich એ બી. એસ. પી. માટે નિશ્ચિત-પરિમાણ ટ્રેક્ટેબિલિટી પરિણામ અને શિરોબિંદુઓ માટે કર્નલ-કદના પરિણામમાં સુધારો કર્યો. એપ્લિકેશન્સ મશીન લર્નિંગ તેના ગાંઠોને લક્ષણો તરીકે અને તેની ધારને અંતર તરીકે ગણતા, મહત્તમ કટ અલ્ગોરિધમ ગ્રાફને બે સારી રીતે અલગ કરેલા ઉપગણમાં વિભાજિત કરે છે. બીજા શબ્દોમાં કહીએ તો, તે કુદરતી રીતે દ્વિસંગી વર્ગીકરણ કરવા માટે લાગુ કરી શકાય છે. વધુ સામાન્ય વર્ગીકરણ અલ્ગોરિધમ્સની તુલનામાં, તેને સુવિધા જગ્યાની જરૂર નથી, માત્ર અંદરના ઘટકો વચ્ચેનું અંતર. સૈદ્ધાંતિક ભૌતિકશાસ્ત્ર આંકડાકીય ભૌતિકશાસ્ત્ર અને અવ્યવસ્થિત પ્રણાલીઓમાં, મેક્સ કટ સમસ્યા સ્પિન ગ્લાસ મોડેલના હેમિલ્ટોનિયનને ઘટાડવાની સમકક્ષ છે, જે સૌથી સરળ રીતે ઇસિંગ મોડેલ છે. ગ્રાફ G પરના આઇસિંગ મોડેલ માટે અને માત્ર નજીકના-પડોશી ક્રિયાપ્રતિક્રિયાઓ માટે, હેમિલ્ટોનિયન છે અહીં ગ્રાફનો દરેક શિરોબિંદુ i એક સ્પિન સાઇટ છે જે સ્પિન મૂલ્ય A સ્પિન રૂપરેખાંકન પાર્ટીશનોને બે સેટમાં લઈ શકે છે, જેમાં સ્પિન અપ અને સ્પિન ડાઉન હોય છે. પછી આપણે હેમિલ્ટોનિયનને ફરીથી લખી શકીએ છીએ કારણ કે આ ઊર્જાને ઘટાડવી એ લઘુતમ કટ સમસ્યાની સમકક્ષ છે અથવા ગ્રાફ વજનને મહત્તમ કટ સમસ્યા તરીકે સેટ કરીને. સર્કિટ ડિઝાઇન મહત્તમ કટ સમસ્યાનો ઉપયોગ વી. એલ. એસ. આઈ. ડિઝાઇનમાં થાય છે. મિનિમમ કટ મિનિમમ કે-કટ ઓડ સાયકલ ટ્રાન્સવર્સલ પણ જુઓ, જે સૌથી મોટા દ્વિપક્ષી પ્રેરિત સબગ્રાફ અનફ્રેન્ડલી પાર્ટીશન માટે પૂછવાની સમકક્ષ છે, જે અનંત ગ્રાફ નોટ્સ રેફરન્સ માટે સંબંધિત ખ્યાલ છે. . મહત્તમ કટ (ઓપ્ટિમાઇઝેશન વર્ઝન) એ પરિશિષ્ટ બી (પાનું 399) માં ND14 સમસ્યા છે. . . . . . . . . . મહત્તમ કાપ (નિર્ણય સંસ્કરણ) એ પરિશિષ્ટ A2.2 માં ND16 સમસ્યા છે. મહત્તમ દ્વિપક્ષી સબગ્રાફ (નિર્ણય સંસ્કરણ) એ પરિશિષ્ટ A1.2 માં GT25 સમસ્યા છે. . . . . . . . . . . . . . . . . . બાહ્ય કડીઓ પિયરલુઇગી ક્રેસેન્ઝી, વિગો કન્ન, મેગ્નસ હેલ્ડોર્સન, મારેક કાર્પિન્સ્કી, ગેરહાર્ડ વોઇજિંગર (2000), "મેક્સિમમ કટ", "એ કોમ્પેન્ડિયમ ઓફ એનપી ઓપ્ટિમાઇઝેશન પ્રોબ્લેમ્સ" માં. એન્ડ્રીયા કેસિની, નિકોલા રિબાગ્લિઆટી (2012), "એ પાયથોન લાઇબ્રેરી ફોર સોલ્વિંગ મેક્સ કટ" ગ્રાફ થિયરી ઓબ્જેક્ટ્સ કોમ્બિનેટરિયલ ઓપ્ટિમાઇઝેશન એન. પી.-પૂર્ણ સમસ્યાઓ ગ્રાફ થિયરીમાં કોમ્પ્યુટેશનલ સમસ્યાઓ