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