Erdős–Gallai theorem
એર્ડોસ-ગલાઈ પ્રમેય એ આલેખ સિદ્ધાંતનું પરિણામ છે, જે સંયુક્ત ગણિતની એક શાખા છે. તે આલેખ અનુભૂતિ સમસ્યાને ઉકેલવા માટેના બે જાણીતા અભિગમોમાંથી એક પ્રદાન કરે છે, એટલે કે. તે કુદરતી સંખ્યાઓના મર્યાદિત ક્રમને સરળ આલેખનો ડિગ્રી ક્રમ બનાવવા માટે જરૂરી અને પૂરતી શરત આપે છે. આ શરતોનું પાલન કરતા ક્રમને "ગ્રાફિક" કહેવામાં આવે છે. આ પ્રમેય 1960માં પોલ એર્દોસ અને ટિબોર ગલાઈ દ્વારા પ્રકાશિત કરવામાં આવ્યો હતો, જેમના નામ પર તેનું નામ રાખવામાં આવ્યું છે. નિવેદન બિન-નકારાત્મક પૂર્ણાંકોના ક્રમને n શિરોબિંદુઓ પર મર્યાદિત સરળ આલેખના ડિગ્રી ક્રમ તરીકે રજૂ કરી શકાય છે જો અને માત્ર ત્યારે જ જો તે સમ હોય અને દરેક માટે સમ હોય. પુરાવા એ બતાવવું મુશ્કેલ નથી કે સંખ્યાઓનો ક્રમ ગ્રાફિક બનવા માટે એર્દોસ-ગલાઈ પ્રમેયની શરતો જરૂરી છે. ડિગ્રીનો સરવાળો સરખો હોવાની જરૂરિયાત હાથ મિલાવવાની વ્યાખ્યા છે, જેનો ઉપયોગ યુલર દ્વારા કોનિગ્સબર્ગના પુલો પરના તેમના 1736ના પેપરમાં પહેલેથી જ કરવામાં આવ્યો હતો. સૌથી મોટી ડિગ્રીના સરવાળા અને બાકીની ડિગ્રીના સરવાળા વચ્ચેની અસમાનતા બેવડી ગણતરી દ્વારા સ્થાપિત કરી શકાય છેઃ ડાબી બાજુ ઉચ્ચતમ-ડિગ્રી શિરોબિંદુઓ વચ્ચે ધાર-વર્ટેક્સ નિકટતાઓની સંખ્યા આપે છે, આવી દરેક નિકટતા કાં તો એક અથવા બે ઉચ્ચ-ડિગ્રી અંતિમ બિંદુઓ સાથે ધાર પર હોવી જોઈએ, જમણી બાજુનો શબ્દ ધાર-વર્ટેક્સ નિકટતાઓની મહત્તમ સંભવિત સંખ્યા આપે છે જેમાં બંને અંતિમ બિંદુઓ ઉચ્ચ ડિગ્રી ધરાવે છે, અને જમણી ઉપરની સીમા પર બાકીની મુદત ધારની સંખ્યા આપે છે જે બરાબર એક ઉચ્ચ ડિગ્રી અંતિમ બિંદુ ધરાવે છે. આમ, સાબિતીનો વધુ મુશ્કેલ ભાગ એ બતાવવાનો છે કે, આ શરતોનું પાલન કરતી સંખ્યાઓના કોઈપણ ક્રમ માટે, એક આલેખ અસ્તિત્વમાં છે જેના માટે તે ડિગ્રી ક્રમ છે. તેનો મૂળ પુરાવો લાંબો અને સંકળાયેલો હતો. નેટવર્ક પ્રવાહના વિચારો પર આધારિત ક્લાઉડ બર્જ દ્વારા ટૂંકા પુરાવા ટાંકવામાં આવ્યા છે. ચૌદુમ તેના બદલે ડિગ્રીના સરવાળા પર ગાણિતિક ઇન્ડક્શન દ્વારા પુરાવો પૂરો પાડે છેઃ તે ક્રમમાં સંખ્યાનો પ્રથમ અનુક્રમણિકા છે (અથવા જો તમામ સમાન હોય તો ઉપાંત્ય સંખ્યા), તે દર્શાવવા માટે કેસ વિશ્લેષણનો ઉપયોગ કરે છે કે ક્રમમાં છેલ્લી સંખ્યામાંથી અને તેમાંથી એકને બાદ કરીને (અને જો આ બાદબાકી તેને શૂન્ય બનાવે તો છેલ્લી સંખ્યાને દૂર કરીને) રચાયેલ ક્રમ ફરીથી ગ્રાફિક છે, અને બે સ્થાનો વચ્ચેની ધાર ઉમેરીને મૂળ ક્રમનું પ્રતિનિધિત્વ કરતો આલેખ બનાવે છે જેમાંથી એકને બાદ કરવામાં આવ્યો હતો. "અવાસ્તવિકતા" ના ક્રમને ધ્યાનમાં લો, આલેખ કે જેની ડિગ્રી આપેલ ડિગ્રી ક્રમ દ્વારા બંધાયેલ હોય છે. તેઓ દર્શાવે છે કે, જો G એ સબરીઅલાઈઝેશન છે, અને i એ G માં શિરોબિંદુની સૌથી નાની અનુક્રમણિકા છે, જેની ડિગ્રી ડીની બરાબર નથી, તો G ને એવી રીતે સુધારી શકાય છે કે જે અન્ય સબરીઅલાઈઝેશન ઉત્પન્ન કરે, જે ક્રમમાં અગાઉના શિરોબિંદુઓની ડિગ્રીમાં ફેરફાર કર્યા વિના શિરોબિંદુ i ની ડિગ્રીમાં વધારો કરે. આ પ્રકારના પુનરાવર્તિત પગલાઓ આખરે આપેલ ક્રમની અનુભૂતિ સુધી પહોંચવું જોઈએ, જે પ્રમેયને સાબિત કરે છે. પૂર્ણાંક પાર્ટીશનો સાથેનો સંબંધ એર્ડોસ-ગલાઈ પ્રમેય અને પૂર્ણાંક પાર્ટીશનોના સિદ્ધાંત વચ્ચેના નજીકના જોડાણોનું વર્ણન કરે છે. ચાલો; પછી સૉર્ટ કરેલ પૂર્ણાંક ક્રમનો સરવાળો તેના પાર્ટીશનો તરીકે અર્થઘટન કરી શકાય છે. તેમના ઉપસર્ગ રકમના મુખ્યકરણ હેઠળ, પાર્ટીશનો એક જાળી બનાવે છે, જેમાં વ્યક્તિગત પાર્ટીશન અને પાર્ટીશન ક્રમમાં નીચલા અન્ય પાર્ટીશન વચ્ચેનો ન્યૂનતમ ફેરફાર એ છે કે એક સંખ્યામાંથી એકને બાદ કરીને તેને ઓછામાં ઓછી બે (શૂન્ય હોઈ શકે છે) દ્વારા નાની સંખ્યામાં ઉમેરવું. એગ્નર અને ટ્રીશ દર્શાવે છે તેમ, આ ઓપરેશન ગ્રાફિક હોવાની મિલકતને જાળવી રાખે છે, તેથી એર્ડોસ-ગલાઈ પ્રમેયને સાબિત કરવા માટે આ મુખ્ય ક્રમમાં મહત્તમ ગ્રાફિક સિક્વન્સની લાક્ષણિકતા દર્શાવવા માટે પૂરતું છે. તેઓ અનુરૂપ પાર્ટીશનોના ફેરર્સ આકૃતિઓના સંદર્ભમાં આવી લાક્ષણિકતા પ્રદાન કરે છે, અને દર્શાવે છે કે તે એર્દોસ-ગલાઈ પ્રમેયની સમકક્ષ છે. અન્ય પ્રકારના આલેખ માટે ગ્રાફિક સિક્વન્સ સમાન પ્રમેયો સરળ નિર્દેશિત આલેખના ડિગ્રી સિક્વન્સ, લૂપ્સ સાથે સરળ નિર્દેશિત આલેખ અને સરળ દ્વિપક્ષી આલેખનનું વર્ણન કરે છે. પ્રથમ સમસ્યાની લાક્ષણિકતા ફુલ્કરસન-ચેન-એન્સ્ટી પ્રમેય દ્વારા દર્શાવવામાં આવી છે. પછીના બે કિસ્સાઓ, જે સમકક્ષ છે, તે ગેલ-રાયસર પ્રમેય દ્વારા વર્ગીકૃત થયેલ છે. મજબૂત સંસ્કરણે સાબિત કર્યું કે તે સાથે અને માટે જેવી અસમાનતાને ધ્યાનમાં લેવા માટે પૂરતું છે. વિપરીત દબાણમાં આલેખ માટે અસમાનતાના સમૂહને મર્યાદિત કરો. જો સમ-સારાંશિત હકારાત્મક ક્રમ d માં મહત્તમ અને લઘુત્તમ (અને લંબાઈ સૌથી મોટી એન્ટ્રી કરતાં વધી જાય છે) સિવાય કોઈ પુનરાવર્તિત એન્ટ્રીઓ ન હોય, તો તે માત્ર છઠ્ઠી અસમાનતાને તપાસવા માટે પૂરતું છે, જ્યાં. સામાન્યીકરણ બિનનફાકારક પૂર્ણાંકોની એક મર્યાદિત શ્રેણી જો સમ હોય તો ગ્રાફિક હોય છે અને ત્યાં એક ક્રમ અસ્તિત્વમાં હોય છે જે ગ્રાફિક હોય છે અને મુખ્ય હોય છે. આ પરિણામ દ્વારા આપવામાં આવ્યું હતું. તેની પુનઃશોધ કરી અને વધુ સીધો પુરાવો આપ્યો. હેવલ-હકીમી અલ્ગોરિધમ સંદર્ભો પણ જુઓ. . આલેખ સિદ્ધાંતમાં ગલ્લાઇ પ્રમેય પ્રમેયો