Bipartite dimension
આલેખ સિદ્ધાંત અને સંયુક્ત ઓપ્ટિમાઇઝેશનના ગાણિતિક ક્ષેત્રોમાં, G = (V, E) આલેખનનું દ્વિપક્ષી પરિમાણ અથવા દ્વિસંગી આવરણ સંખ્યા એ દ્વિસંગીઓની લઘુતમ સંખ્યા છે (જે સંપૂર્ણ દ્વિસંગી ઉપલેખ છે), જે E માં તમામ ધારને આવરી લેવા માટે જરૂરી છે. G માં તમામ ધારને આવરી લેતી દ્વિસંગીઓનો સંગ્રહ દ્વિસંગી ધાર આવરણ અથવા કેટલીકવાર દ્વિસંગી આવરણ કહેવાય છે. G ના દ્વિપક્ષી પરિમાણને ઘણીવાર પ્રતીક d (G) દ્વારા દર્શાવવામાં આવે છે. ઉદાહરણ દ્વિ-ચક્રીય ધાર આવરણનું ઉદાહરણ નીચેની આકૃતિઓમાં આપવામાં આવ્યું છેઃ કેટલાક આલેખ માટે દ્વિ-પક્ષીય પરિમાણ સૂત્રો એન-વર્ટેક્સ સંપૂર્ણ આલેખનનું દ્વિ-પક્ષીય પરિમાણ છે. 2n-વર્ટેક્સ ક્રાઉન ગ્રાફનું દ્વિપક્ષી પરિમાણ બરાબર છે, જ્યાં કેન્દ્રીય દ્વિપદી ગુણાંકનું વ્યસ્ત કાર્ય છે. જાળી આલેખનું દ્વિપક્ષી પરિમાણ છે, જો સમ હોય અને કેટલાક પૂર્ણાંકો માટે; અને અન્યથા છે. કેટલાક વિશેષ આલેખ માટે દ્વિપક્ષી પરિમાણ નક્કી કરો. ઉદાહરણ તરીકે, માર્ગ પાસે છે અને ચક્ર પાસે છે. દ્વિદલીય પરિમાણની ગણતરી આપેલ આલેખ G માટે દ્વિદલીય પરિમાણ નક્કી કરવાનું કોમ્પ્યુટેશનલ કાર્ય એક ઓપ્ટિમાઇઝેશન સમસ્યા છે. દ્વિપક્ષી પરિમાણ માટેની નિર્ણય સમસ્યાને આ રીતે રજૂ કરી શકાય છેઃ તાત્કાલિકઃ આલેખ અને હકારાત્મક પૂર્ણાંક. પ્રશ્નઃ શું G મોટાભાગે દ્વિશિરક ધરાવતું દ્વિશિરક ધાર આવરણ સ્વીકારે છે? આ સમસ્યા ગેરે અને જ્હોનસનના એન. પી.-પૂર્ણતા પરના શાસ્ત્રીય પુસ્તકમાં સમસ્યા જી. ટી. 18 તરીકે દેખાય છે, અને તે મર્યાદિત સમૂહોના પરિવારો પર અન્ય નિર્ણય સમસ્યાનું સીધું પુનરાવર્તન છે. ગેરે અને જ્હોનસનના પુસ્તકમાં નિર્ધારિત પાયાની સમસ્યા એસ. પી. 7 તરીકે દેખાય છે. અહીં, મર્યાદિત સમૂહના ઉપગણના પરિવાર માટે, એક સમૂહ આધાર એ ઉપગણોનો બીજો પરિવાર છે, જેમ કે દરેક સમૂહને તેમાંથી કેટલાક આધાર તત્વોના જોડાણ તરીકે વર્ણવી શકાય છે. સમૂહ આધાર સમસ્યા હવે નીચે પ્રમાણે આપવામાં આવી છેઃ તાત્કાલિકઃ એક મર્યાદિત સમૂહ, ના ઉપગણોનું કુટુંબ અને હકારાત્મક પૂર્ણાંક k. પ્રશ્નઃ શું કદ માટે મહત્તમ એક સમૂહ આધાર અસ્તિત્વમાં છે? તેની અગાઉની રચનામાં, દ્વિદલીય આલેખ માટે પણ આ સમસ્યા એન. પી.-પૂર્ણ સાબિત થઈ હતી. સેટ બેઝીસ પ્રોબ્લેમ તરીકેની રચના અગાઉ દ્વારા એન. પી.-પૂર્ણ સાબિત થઈ હતી. જો આપણે આપણું ધ્યાન દ્વિપક્ષી આલેખ પર મર્યાદિત રાખીએ તો પણ સમસ્યા એન. પી.-સખત રહે છે, જેનું દ્વિપક્ષી પરિમાણ મહત્તમ હોવાની ખાતરી આપવામાં આવે છે, જેમાં n આપેલ સમસ્યાના ઉદાહરણના કદને સૂચવે છે. હકારાત્મક બાજુએ, દ્વિદલીય ડોમીનો-મુક્ત આલેખ પર બહુપદી સમયમાં સમસ્યાનું સમાધાન કરી શકાય છે. અંદાજિત અલ્ગોરિધમ્સના અસ્તિત્વ અંગે, સાબિત કર્યું કે સમસ્યાને સારી રીતે અંદાજિત કરી શકાતી નથી (P § NP ધારીને). ખરેખર, દ્વિદલીય પરિમાણ એન. પી.-હાર્ડથી દરેક નિશ્ચિત માટે અંદાજિત છે, પહેલેથી જ દ્વિદલીય આલેખ માટે. તેનાથી વિપરીત, સમસ્યા ફિક્સ્ડ-પેરામીટર ટ્રેક્ટેબલ છે તે સાબિત કરવું એ કર્નલાઇઝેશન અલ્ગોરિધમ્સ ડિઝાઇન કરવાની કવાયત છે, જે દ્વારા પાઠ્યપુસ્તકમાં દેખાય છે. પરિણામી કર્નલના કદ પર કોંક્રિટ બાઉન્ડ પણ પ્રદાન કરે છે, જે દરમિયાન દ્વારા સુધારવામાં આવ્યો છે. હકીકતમાં, n શિરોબિંદુઓ પર આપેલ દ્વિપક્ષી આલેખ માટે, તે સમયસર નક્કી કરી શકાય છે કે તેનું દ્વિપક્ષી પરિમાણ મહત્તમ k એપ્લિકેશન્સ પર છે કે કેમ ગ્રાફનું દ્વિપક્ષી પરિમાણ નક્કી કરવાની સમસ્યા કમ્પ્યુટિંગના વિવિધ સંદર્ભોમાં દેખાય છે. દાખલા તરીકે, કોમ્પ્યુટર સિસ્ટમોમાં, સિસ્ટમના વિવિધ વપરાશકર્તાઓને વિવિધ સંસાધનો સુધી પહોંચવાની મંજૂરી અથવા મંજૂરી આપી શકાતી નથી. ભૂમિકા-આધારિત પ્રવેશ નિયંત્રણ પ્રણાલીમાં, ભૂમિકા સંસાધનોના સમૂહને પ્રવેશ અધિકારો પ્રદાન કરે છે. વપરાશકર્તા બહુવિધ ભૂમિકાઓ ધરાવી શકે છે, અને તેની પાસે તેની કેટલીક ભૂમિકાઓ દ્વારા આપવામાં આવેલા તમામ સંસાધનોને ઍક્સેસ કરવાની પરવાનગી છે. ઉપરાંત, એક ભૂમિકા બહુવિધ વપરાશકર્તાઓની માલિકીની હોઈ શકે છે. ભૂમિકા ખનનની સમસ્યા ભૂમિકાઓનો ઓછામાં ઓછો સમૂહ શોધવાની છે, જેમ કે દરેક વપરાશકર્તા માટે, તેની ભૂમિકાઓ એકસાથે લેવામાં આવે તો તે તમામ ચોક્કસ સંસાધનોની પહોંચ આપે છે. સિસ્ટમમાં સંસાધનોના સમૂહ સાથે વપરાશકર્તાઓનો સમૂહ કુદરતી રીતે દ્વિપક્ષી આલેખને પ્રેરિત કરે છે, જેની ધાર પરવાનગીઓ છે. આ આલેખમાં દરેક બાયક્લિક સંભવિત ભૂમિકા છે, અને ભૂમિકા ખાણકામ સમસ્યાના મહત્તમ ઉકેલો ચોક્કસપણે ન્યૂનતમ બાયક્લિક ધાર આવરણ છે. સમાન દૃશ્ય કમ્પ્યુટર સુરક્ષામાં જાણીતું છે, ખાસ કરીને સુરક્ષિત પ્રસારણમાં. તે સેટઅપમાં, અસુરક્ષિત ચેનલ પર, દરેકને પ્રાપ્તકર્તાઓના સમૂહને ઘણા સંદેશા મોકલવાની જરૂર છે. દરેક સંદેશને અમુક ક્રિપ્ટોગ્રાફિક કીનો ઉપયોગ કરીને એન્ક્રિપ્ટ કરવો પડે છે જે ફક્ત ઇચ્છિત પ્રાપ્તકર્તાઓને જ ખબર હોય છે. દરેક રીસીવર પાસે બહુવિધ એન્ક્રિપ્શન કીઓ હોઈ શકે છે, અને દરેક કી બહુવિધ રીસીવરોમાં વહેંચવામાં આવશે. શ્રેષ્ઠ કી જનરેશન સમસ્યા એ છે કે સુરક્ષિત પ્રસારણની ખાતરી કરવા માટે એન્ક્રિપ્શન કીઓનો ઓછામાં ઓછો સમૂહ શોધવો. ઉપરની જેમ, સમસ્યાને દ્વિપક્ષી આલેખનો ઉપયોગ કરીને મોડેલિંગ કરી શકાય છે, જેની લઘુતમ બાયક્લિક ધાર મહત્તમ કી જનરેશન સમસ્યાના ઉકેલો સાથે મેળ ખાય છે. એક અલગ ઉપયોગ જીવવિજ્ઞાનમાં છે, જ્યાં માનવ લ્યુકોસાઇટ એન્ટિજેન (એચ. એલ. એ.) સેરોલોજીના ગાણિતિક નમૂનાઓમાં લઘુત્તમ બાયક્લિક ધાર આવરણનો ઉપયોગ થાય છે. એન. પી.-પૂર્ણ સમસ્યાઓની યાદી પણ જુઓ આંતરછેદ સંખ્યા (આલેખ સિદ્ધાંત), આલેખ સંદર્ભોની ધારને આવરી લેવા માટે જરૂરી જૂથોની લઘુતમ સંખ્યા. . . . . . . . . . . . . . . બાહ્ય લિંક્સ ડેવિડ એપસ્ટીન દ્વારા દ્વિપક્ષી પરિમાણ વિશે બ્લોગ એન્ટ્રી એન. પી.-પૂર્ણ સમસ્યાઓ ગ્રાફ અપરિવર્તનશીલ દ્વિપક્ષી આલેખ આવરી લેતી સમસ્યાઓ