Split graph
આલેખ સિદ્ધાંતમાં, ગણિતની એક શાખા, વિભાજીત આલેખ એ એક આલેખ છે જેમાં શિરોબિંદુઓને જૂથ અને સ્વતંત્ર સમૂહમાં વિભાજિત કરી શકાય છે. સ્પ્લિટ ગ્રાફનો સૌપ્રથમ અભ્યાસ તેમના દ્વારા કરવામાં આવ્યો હતો અને સ્વતંત્ર રીતે તેમના દ્વારા રજૂ કરવામાં આવ્યો હતો. વિભાજીત આલેખમાં જૂથ અને સ્વતંત્ર સમૂહમાં એક કરતાં વધુ પાર્ટીશન હોઈ શકે છે; દાખલા તરીકે, પાથ એ વિભાજીત આલેખ છે, જેના શિરોબિંદુઓને ત્રણ અલગ અલગ રીતે વિભાજિત કરી શકાય છેઃ જૂથ અને સ્વતંત્ર સમૂહ જૂથ અને સ્વતંત્ર સમૂહ જૂથ અને સ્વતંત્ર સમૂહ જૂથ અને સ્વતંત્ર સમૂહ વિભાજન આલેખ તેમના પ્રતિબંધિત પ્રેરિત પેટા આલેખની દ્રષ્ટિએ વર્ગીકૃત કરી શકાય છેઃ આલેખ વિભાજિત થાય છે જો અને માત્ર ત્યારે જ જો કોઈ પ્રેરિત પેટા આલેખ ચાર કે પાંચ શિરોબિંદુઓ પરનું ચક્ર ન હોય, અથવા અસંબદ્ધ ધારની જોડી (4-ચક્રનું પૂરક) હોય. અન્ય આલેખ પરિવારો સાથે સંબંધ વ્યાખ્યામાંથી, વિભાજીત આલેખ સ્પષ્ટ રીતે પૂરકતા હેઠળ બંધ કરવામાં આવે છે. વિભાજીત આલેખની અન્ય લાક્ષણિકતામાં પૂરકતાનો સમાવેશ થાય છેઃ તે કોર્ડલ આલેખ છે, જેના પૂરક પણ કોર્ડલ છે. જેમ કોર્ડલ આલેખ એ વૃક્ષોના પેટા વૃક્ષોના આંતરછેદના આલેખ છે, તેમ વિભાજીત આલેખ એ તારા આલેખના અલગ સબસ્ટાર્સના આંતરછેદના આલેખ છે. લગભગ તમામ કોર્ડલ આલેખ વિભાજિત આલેખ છે; એટલે કે, n અનંત તરફ જાય છે તે મર્યાદામાં, વિભાજિત n-વર્ટેક્સ કોર્ડલ આલેખનો અપૂર્ણાંક એક તરફ પહોંચે છે. કારણ કે કોર્ડલ આલેખ સંપૂર્ણ છે, તેથી વિભાજીત આલેખ પણ સંપૂર્ણ છે. ડબલ સ્પ્લિટ ગ્રાફ, દરેક શિરોબિંદુને બમણો કરીને સ્પ્લિટ ગ્રાફમાંથી મેળવેલા ગ્રાફનું એક કુટુંબ છે (તેથી ક્લીક એન્ટિમેચિંગને પ્રેરિત કરવા માટે આવે છે અને સ્વતંત્ર સમૂહ મેચિંગને પ્રેરિત કરવા માટે આવે છે), સંપૂર્ણ ગ્રાફના પાંચ મૂળભૂત વર્ગોમાંથી એક તરીકે મુખ્યત્વે આકૃતિ આપે છે જેમાંથી અન્ય તમામને મજબૂત સંપૂર્ણ ગ્રાફ પ્રમેય દ્વારા સાબિતીમાં બનાવી શકાય છે. જો આલેખ વિભાજિત આલેખ અને અંતરાલ આલેખ બંને હોય, તો તેનું પૂરક વિભાજિત આલેખ અને તુલનાત્મક આલેખ બંને છે, અને તેનાથી ઊલટું. વિભાજીત તુલનાત્મક આલેખ, અને તેથી વિભાજીત અંતરાલ આલેખ, ત્રણ પ્રતિબંધિત પ્રેરિત સબગ્રાફ્સના સમૂહની દ્રષ્ટિએ વર્ગીકૃત કરી શકાય છે. વિભાજીત આલેખ બરાબર થ્રેશોલ્ડ આલેખ છે. વિભાજીત ક્રમચય આલેખ બરાબર અંતરાલ આલેખ છે જેમાં અંતરાલ આલેખ પૂરક હોય છે; આ વક્ર-વિલયિત ક્રમચયોના ક્રમચય આલેખ છે. સ્પ્લિટ ગ્રાફમાં કોક્રોમેટિક નંબર 2 હોય છે. એલ્ગોરિધમિક સમસ્યાઓ ચાલો વિભાજીત આલેખ હોઈએ, જે જૂથ અને સ્વતંત્ર સમૂહમાં વિભાજિત થાય છે. પછી વિભાજીત આલેખમાં દરેક મહત્તમ જૂથ કાં તો પોતે જ હોય છે, અથવા તેમાં શિરોબિંદુની પડોશ હોય છે. આમ, સ્પ્લિટ ગ્રાફમાં મહત્તમ જૂથ અને પૂરક રીતે મહત્તમ સ્વતંત્ર સમૂહને ઓળખવું સરળ છે. કોઈપણ વિભાજીત આલેખમાં, નીચેની ત્રણ શક્યતાઓમાંથી એક સાચી હોવી જોઈએઃ તેમાં એક શિરોબિંદુ અસ્તિત્વમાં છે જે પૂર્ણ છે. આ કિસ્સામાં, તે મહત્તમ જૂથ છે અને મહત્તમ સ્વતંત્ર સમૂહ છે. તેમાં એક શિરોબિંદુ અસ્તિત્વમાં છે જે સ્વતંત્ર છે. આ કિસ્સામાં, તે મહત્તમ સ્વતંત્ર સમૂહ છે અને મહત્તમ જૂથ છે. તે મહત્તમ જૂથ છે અને મહત્તમ સ્વતંત્ર સમૂહ છે. આ કિસ્સામાં, એક જૂથ અને એક સ્વતંત્ર સમૂહમાં એક અનન્ય વિભાજન છે, તે મહત્તમ જૂથ છે, અને તે મહત્તમ સ્વતંત્ર સમૂહ છે. કેટલીક અન્ય ઓપ્ટિમાઇઝેશન સમસ્યાઓ કે જે વધુ સામાન્ય ગ્રાફ પરિવારો પર એન. પી.-પૂર્ણ છે, જેમાં ગ્રાફ રંગનો સમાવેશ થાય છે, તે જ રીતે વિભાજીત ગ્રાફ પર સીધી છે. હેમિલ્ટોનિયન ચક્ર શોધવું એ વિભાજીત આલેખ માટે પણ એન. પી.-પૂર્ણ રહે છે જે મજબૂત કોર્ડલ આલેખ છે. તે પણ જાણીતું છે કે સ્પ્લિટ ગ્રાફ માટે મિનિમમ ડોમિનેટિંગ સેટ સમસ્યા એન. પી.-પૂર્ણ રહે છે. વિભાજીત આલેખનો એક નોંધપાત્ર ગુણધર્મ એ છે કે તેઓ માત્ર તેમના ડિગ્રી ક્રમથી ઓળખી શકાય છે. આલેખનો ડિગ્રી ક્રમ હોવો જોઈએ, અને તેનું સૌથી મોટું મૂલ્ય હોવું જોઈએ. જો આ કિસ્સો હોય, તો પછી સૌથી મોટી ડિગ્રીવાળા શિરોબિંદુઓ મહત્તમ સમૂહ બનાવે છે, અને બાકીના શિરોબિંદુઓ એક સ્વતંત્ર સમૂહ બનાવે છે. મનસ્વી ગ્રાફનું વિભાજન એ માપે છે કે આ અસમાનતા કેટલી હદ સુધી સાચી નથી. જો આલેખ વિભાજીત આલેખ ન હોય, તો તેને વિભાજીત આલેખમાં પરિવર્તિત કરતી ધાર દાખલ કરવા અને દૂર કરવાનો સૌથી નાનો ક્રમ, શિરોબિંદુઓ વચ્ચેની તમામ ગુમ થયેલી ધારને સૌથી મોટી ડિગ્રી સાથે ઉમેરીને અને બાકીના શિરોબિંદુઓની જોડી વચ્ચેની તમામ ધારને દૂર કરીને મેળવી શકાય છે; વિભાજન આ ક્રમમાં કામગીરીની સંખ્યાની ગણતરી કરે છે. વિભાજીત આલેખની ગણતરી દર્શાવે છે કે n સાથે n-વર્ટેક્સ વિભાજીત આલેખ ચોક્કસ સ્પર્નર પરિવારો સાથે એક-થી-એક પત્રવ્યવહારમાં છે. આ હકીકતનો ઉપયોગ કરીને, તેમણે n શિરોબિંદુઓ પર બિન-આઇસોમોર્ફિક વિભાજીત આલેખની સંખ્યા માટે સૂત્ર નક્કી કર્યું. n ના નાના મૂલ્યો માટે, n = 1 થી શરૂ કરીને, આ સંખ્યાઓ 1,2,4,9,21,56,164,557,2223,10766,64956,501696, છે. આ ગણનાત્મક પરિણામ પણ અગાઉ દ્વારા સાબિત કરવામાં આવ્યું હતું. નોંધો સંદર્ભો. . . . . . . . . . . . . . . યુ. એસ. એસ. આર. 48 (6) ની એકેડેમી ઓફ સાયન્સિસની ગાણિતિક નોંધોઃ 1239-1245, "અચિહ્નિત સંયુક્ત પદાર્થોની ગણતરી કરવાની બીજી પદ્ધતિ" (1990) તરીકે અનુવાદિત. . . સ્પ્લિટ ગ્રાફ પરનું એક પ્રકરણ માર્ટિન ચાર્લ્સ ગોલુમ્બિકના પુસ્તક "એલ્ગોરિધમિક ગ્રાફ થિયરી એન્ડ પરફેક્ટ ગ્રાફ્સ" માં જોવા મળે છે. આલેખ પરિવારો આલેખના આંતરછેદના વર્ગો સંપૂર્ણ આલેખ