Erdős–Gallai theorem
एर्डोस-गलाई प्रमेय ग्राफ सिद्धांत का एक परिणाम है, जो संयोजी गणित की एक शाखा है। यह ग्राफ प्राप्ति समस्या को हल करने के लिए दो ज्ञात दृष्टिकोणों में से एक प्रदान करता है, अर्थात। यह प्राकृतिक संख्याओं के एक सीमित अनुक्रम के लिए एक सरल ग्राफ का डिग्री अनुक्रम होने के लिए एक आवश्यक और पर्याप्त शर्त देता है। इन शर्तों का पालन करने वाले अनुक्रम को "ग्राफिक" कहा जाता है। यह प्रमेय 1960 में पॉल एर्दोस और टिबोर गैलाई द्वारा प्रकाशित किया गया था, जिनके नाम पर इसका नाम रखा गया है। कथन गैर-ऋणात्मक पूर्णांकों के एक अनुक्रम को n शीर्षों पर एक परिमित सरल ग्राफ के डिग्री अनुक्रम के रूप में दर्शाया जा सकता है यदि और केवल तभी जब यह सम हो और प्रत्येक के लिए सम हो। सबूत यह दिखाना मुश्किल नहीं है कि एर्डोस-गलाई प्रमेय की शर्तें संख्याओं के अनुक्रम के ग्राफिक होने के लिए आवश्यक हैं। डिग्री का योग सम होने की आवश्यकता हाथ मिलाने वाला लेम्मा है, जिसका उपयोग यूलर ने पहले से ही कोनिग्सबर्ग के पुलों पर अपने 1736 के पेपर में किया था। सबसे बड़ी डिग्री के योग और शेष डिग्री के योग के बीच असमानता को दोहरी गिनती द्वारा स्थापित किया जा सकता हैः बाईं ओर उच्चतम-डिग्री शीर्षों के बीच किनारे-वर्टेक्स निकटताओं की संख्या दी जाती है, ऐसी प्रत्येक निकटता या तो एक या दो उच्च-डिग्री अंतिम बिंदुओं के साथ एक किनारे पर होनी चाहिए, दाईं ओर का शब्द किनारे-वर्टेक्स निकटताओं की अधिकतम संभव संख्या देता है जिसमें दोनों अंतिम बिंदुओं में उच्च डिग्री होती है, और दाईं ऊपरी सीमा पर शेष पद किनारों की संख्या देता है जिसमें बिल्कुल एक उच्च डिग्री अंतिम बिंदु होता है। इस प्रकार, प्रमाण का अधिक कठिन हिस्सा यह दिखाना है कि, इन शर्तों का पालन करने वाली संख्याओं के किसी भी अनुक्रम के लिए, एक ग्राफ मौजूद है जिसके लिए यह डिग्री अनुक्रम है। इसका मूल प्रमाण लंबा और शामिल था। नेटवर्क प्रवाह के विचारों के आधार पर क्लाउड बर्ज द्वारा एक छोटे प्रमाण का हवाला दिया गया है। चौदुम इसके बजाय डिग्री के योग पर गणितीय प्रेरण द्वारा एक प्रमाण प्रदान करता हैः वह उस अनुक्रम में एक संख्या का पहला सूचकांक होने देता है जिसके लिए (या यदि सभी समान हैं तो उपांत संख्या), एक मामले के विश्लेषण का उपयोग यह दिखाने के लिए करता है कि अनुक्रम में अंतिम संख्या से एक को घटाने से बना अनुक्रम (और अंतिम संख्या को हटाने से यदि यह घटाव शून्य हो जाता है) फिर से ग्राफिक है, और दो स्थितियों के बीच एक किनारे को जोड़कर मूल अनुक्रम का प्रतिनिधित्व करने वाला एक ग्राफ बनाता है जिससे एक को घटाया गया था। "अवास्तविकता" के एक अनुक्रम पर विचार करें, ग्राफ जिनकी डिग्री दी गई डिग्री अनुक्रम से ऊपरी सीमा में हैं। वे बताते हैं कि, यदि G एक अवास्तविकता है, और i G में एक शीर्ष का सबसे छोटा सूचकांक है, जिसकी डिग्री डी के बराबर नहीं है, तो G को इस तरह से संशोधित किया जा सकता है जो अनुक्रम में पहले के शीर्षों की डिग्री को बदले बिना शीर्ष i की डिग्री को बढ़ाते हुए एक और अवास्तविकता पैदा करता है। इस तरह के दोहराए गए चरणों को अंततः दिए गए अनुक्रम की प्राप्ति तक पहुंचना चाहिए, जो प्रमेय को साबित करता है। पूर्णांक विभाजनों से संबंध एर्दोस-गलाई प्रमेय और पूर्णांक विभाजनों के सिद्धांत के बीच घनिष्ठ संबंधों का वर्णन करता है। मान लीजिए; फिर क्रमबद्ध पूर्णांक अनुक्रमों का योग विभाजन के रूप में व्याख्या की जा सकती है। उनके उपसर्ग योग के प्रमुखकरण के तहत, विभाजन एक जाली बनाते हैं, जिसमें एक व्यक्तिगत विभाजन और विभाजन क्रम में निचले हिस्से में एक अन्य विभाजन के बीच न्यूनतम परिवर्तन एक संख्या से एक को घटाना और इसे एक संख्या में जोड़ना है जो कम से कम दो से छोटा है (शून्य हो सकता है)। जैसा कि ऐग्नर और ट्रिश दिखाते हैं, यह ऑपरेशन ग्राफिक होने के गुण को संरक्षित करता है, इसलिए एर्डोस-गैलाई प्रमेय को साबित करने के लिए यह ग्राफिक अनुक्रमों को चिह्नित करने के लिए पर्याप्त है जो इस प्रमुखता क्रम में अधिकतम हैं। वे संबंधित विभाजनों के फेरर्स आरेखों के संदर्भ में इस तरह का एक लक्षण वर्णन प्रदान करते हैं, और दिखाते हैं कि यह एर्डोस-गैलाई प्रमेय के बराबर है। अन्य प्रकार के आलेखों के लिए ग्राफिक अनुक्रम इसी तरह के प्रमेय सरल निर्देशित आलेखों के डिग्री अनुक्रमों, लूप के साथ सरल निर्देशित आलेखों और सरल द्विदलीय आलेखों का वर्णन करते हैं। पहली समस्या की विशेषता फुल्करसन-चेन-एंस्टी प्रमेय है। बाद के दो मामले, जो समतुल्य हैं, गेल-रेसर प्रमेय द्वारा चिह्नित किए जाते हैं। मजबूत संस्करण ने साबित किया कि यह असमानता पर विचार करने के लिए पर्याप्त है जैसे कि के साथ और के लिए। एक विपरीत जोर में ग्राफ के लिए असमानताओं के सेट को सीमित करें। यदि सम-सारांशित धनात्मक अनुक्रम d में अधिकतम और न्यूनतम (और लंबाई सबसे बड़ी प्रविष्टि से अधिक है) के अलावा कोई बार-बार प्रविष्टियाँ नहीं हैं, तो यह केवल th असमानता की जाँच करने के लिए पर्याप्त है, जहाँ। सामान्यीकरण गैर-ऋणात्मक पूर्णांकों का एक सीमित अनुक्रम ग्राफिक है यदि सम है और एक अनुक्रम मौजूद है जो ग्राफिक है और प्रमुख है। यह परिणाम दिया गया था। इसका पुनः आविष्कार किया और अधिक प्रत्यक्ष प्रमाण दिया। हावेल-हकीमी एल्गोरिदम संदर्भ भी देखें। .. ग्राफ सिद्धांत में गैलाई प्रमेय प्रमेय