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