अत्यधिक संयोजनिकी
अत्यधिक संयोजनिकी गणित का एक आकर्षक क्षेत्र है जो असतत संरचनाओं के अत्यधिक (अधिकतम या न्यूनतम) गुणधर्मों के अध्ययन पर ध्यान केंद्रित करता है। इन संरचनाओं में ग्राफ, हाइपरग्राफ, सेट, क्रमिकाएं, और अन्य संयोजकीय वस्तुएं शामिल हो सकती हैं। अत्यधिक संयोजनिकी के प्रमुख प्रश्न अक्सर यह निर्धारित करने के इर्द-गिर्द घूमते हैं कि एक संग्रह का अधिकतम या न्यूनतम आकार क्या है जो दिए गए शर्तों को पूरा करता है। यह निश्चित गुणधर्मों वाले सबसे बड़े ग्राफ या विशिष्ट शर्तों को पूरा करने वाले सबसे छोटे सेट का निर्धारण करने में शामिल हो सकता है।
मूलभूत अवधारणाएँ और परिभाषाएँ
अत्यधिक संयोजनिकी में उतरने के लिए, हमें पहले कुछ मूलभूत अवधारणाओं और परिभाषाओं को समझना होगा जो इस क्षेत्र की नींव बनाते हैं।
ग्राफ और उपग्राफ
ग्राफ शीर्षकों (या नोड) और शीर्षकों के जोड़ों को जोड़ने वाली धाराओं का संग्रह है। उपग्राफ ग्राफ के शीर्षकों का एक उपसमुच्चय होता है, साथ ही उन्हें जोड़ने वाली सभी धाराएँ भी इसमें शामिल होती हैं।
हाइपरग्राफ
हाइपरग्राफ धाराओं को दो से अधिक शीर्षकों को जोड़ने की अनुमति देकर एक ग्राफ की अवधारणा को आम बनाता है। इन धाराओं को अक्सर हाइपरधाराएँ कहा जाता है और ये किसी भी संख्या में शीर्षकों को समाहित कर सकती हैं।
सेट और क्रमिकाएं
संयोजनिकी में, सेट अलग-अलग वस्तुओं या संख्याओं का संग्रह होते हैं, जबकि क्रमिकाएं वस्तुओं या संख्याओं का क्रमबद्ध संग्रह होती हैं। सेट और क्रमिकाएँ अक्सर विभिन्न समस्याओं का अध्ययन करने के लिए प्रयोग की जाती हैं, जैसे अधिकतम प्रतिच्छेदन या ओवरलैपिंग क्रमिकाएं।
अत्यधिक संयोजनिकी के प्रमुख प्रमेय
कई प्रमुख प्रमेय अत्यधिक संयोजनिकी की नींव बनाते हैं। ये प्रमेय अक्सर संयोजकीय संरचनाओं के अधिकतम या न्यूनतम गुणधर्मों पर अंतर्दृष्टि या सीमाएँ प्रदान करते हैं।
टूरान का प्रमेय
अत्यधिक ग्राफ सिद्धांत में सबसे प्रसिद्ध परिणामों में से एक टूरान का प्रमेय है। यह प्रमेय उस ग्राफ़ में किनारों की संख्या पर एक सीमा प्रदान करता है जिसकी एक पूर्ण उपग्राफ की निश्चित आकार की कमी होती है।
टूरान का प्रमेय: एक ग्राफ के लिए जिसमें n शीर्षक होते हैं और जो r + 1 शीर्षकों की पूर्ण उपग्राफ शामिल नहीं करता है, अधिकतम किनारों की संख्या होती है:
T_r(n) = left(1 - frac{1}{r} right) frac{n^2}{2}यह संकेत करता है कि यदि आप एक ऐसा ग्राफ चाहते हैं जो r + 1 शीर्षकों का पूर्ण ग्राफ शामिल नहीं करता है, तो किनारों की संख्या उपरोक्त सूत्र द्वारा सीमित होती है।
उदाहरण के लिए, यदि n = 5 और r = 2, तो अधिकतम संख्या जिसमें एक त्रिभुज-रहित ग्राफ हो सकता है:
T_2(5) = left(1 - frac{1}{2} right) frac{5^2}{2} = frac{1}{2} cdot frac{25}{2} = 6.25इस प्रकार, 5 शीर्षकों वाले त्रिभुज-रहित ग्राफ में अधिकतम 6 किनारे हो सकते हैं।
एर्डोश-स्टोन प्रमेय
एर्डोश-स्टोन प्रमेय टूरान प्रमेय का सामान्य संस्करण है और अत्यधिक ग्राफ सिद्धांत का एक आधारशिला है, जो किसी भी ग्राफ के लिए अधिकतम संख्या दर्शाता है, जिसका क्रोमैटिक संख्या 2 से अधिक है।
एर्डोश-स्टोन प्रमेय: यदि एक ग्राफ G में एक पूर्ण उपग्राफ K_{r+1} नहीं है, तो अधिकतम किनारों की संख्या लगभग होती है:
ex(n, K_{r+1}) = left(1 - frac{1}{r} + o(1) right) frac{n^2}{2}उपरोक्त SVG एक त्रिभुज दर्शाता है।
अत्यधिक समुच्चय सिद्धांत
अत्यधिक समुच्चय सिद्धांत आमतौर पर समुच्चयों के परिवारों के बारे में प्रश्नों से संबंधित होता है। प्रसिद्ध एर्डोश-को-राडो प्रमेय इस क्षेत्र में सबसे गहरी परिणामों में से एक है।
एर्डोश-को-राडो प्रमेय
यह प्रमेय किसी समुच्चय परिवार के आकार की ऊपरी सीमा प्रदान करता है, यदि सभी समुच्चय कम से कम तय संख्या में तत्वों के साथ प्रतिच्छेद करते हैं।
एर्डोश-को-राडो प्रमेय: मान लीजिए k ≤ n/2 और F k- तत्वों के उपसमुच्चयों का एक समुच्चय परिवार है {1, 2, ..., n}. यदि F में हर दो सेट एक-दूसरे को प्रतिच्छेद करते हैं, तो |F| ≤ C(n-1, k-1). इस सीमा को तब प्राप्त किया जाता है जब F एक निश्चित तत्व वाले सभी k- तत्वों के सेटों से बना होता है।
के लिए n = 5 और k = 2, सेटों का परिवार { {1,2}, {2,3}, {3,4}, {4,5}, {5,1} } एक सीमा प्राप्त करता है जब सभी शीर्षकों के जोड़े एक-दूसरे को प्रतिच्छेदन करते हैं।
आवेदन और समस्याएं
अत्यधिक संयोजनिकी का कई क्षेत्रों में, जैसे कि कंप्यूटर विज्ञान, सूचना सिद्धांत, और डिजाइन सिद्धांत में अनुप्रयोग होते हैं। यह समस्याओं को हल करने में मददगार है जो दिए गए बाधाओं के तहत कुछ मात्राओं को अधिकतम या न्यूनतम बनाने में शामिल होते हैं।
समस्या 1: एक त्रिभुज-रहित ग्राफ को अधिकतम बनाना
यदि एक ग्राफ में n शीर्षक होते हैं, तो इसमें त्रिभुज का निर्माण किए बिना अधिकतम कितने किनारे हो सकते हैं?
टूरान के प्रमेय के अनुसार, इसका उत्तर है:
T_2(n) = left(1 - frac{1}{2} right) frac{n^2}{2} = frac{n^2}{4}समस्या 2: असंगत सेटों का सबसे बड़ा परिवार
मान लीजिए आपके पास एक सेट के उपसमुच्चय हैं जिसकी आकार n है, और आप उपसमुच्चयों का सबसे बड़ा परिवार चाहते हैं ताकि कोई दो उपसमुच्चय जोड़े असंगत न हों। इस समस्य
टिप्पणियाँ