एक्सट्रीमल ग्राफ सिद्धांत

तुरान ग्राफ T(n,r) एक्सट्रीमल ग्राफ का उदाहरण है। इसमें (r + 1)-क्लिक (ग्राफ़ सिद्धांत) के बिना n शीर्षों पर ग्राफ़ के लिए किनारों की अधिकतम संभव संख्या है। यह T(13,4) है।

एक्सट्रीमल ग्राफ सिद्धांत साहचर्य की शाखा है, जो स्वयं गणित का क्षेत्र है, जो एक्सट्रीमल कॉम्बिनेटरिक्स और ग्राफ सिद्धांत के अन्तः खंड पर स्थित है। संक्षेप में, एक्सट्रीमल ग्राफ़ सिद्धांत अध्ययन करता है कि ग्राफ़ के वैश्विक गुण स्थानीय उपसंरचना को कैसे प्रभावित करते हैं। एक्सट्रीमल ग्राफ़ सिद्धांत में परिणाम विभिन्न ग्राफ़ गुणों के मध्य मात्रात्मक कनेक्शन से सम्बंधित हैं, दोनों वैश्विक (जैसे कोने और किनारों की संख्या) और स्थानीय (जैसे विशिष्ट उपग्राफों का अस्तित्व), और एक्सट्रीमल ग्राफ़ सिद्धांत में समस्याओं को प्रायःअनुकूलन के रूप में प्रस्तुत किया जा सकता है समस्याएँ: ग्राफ़ का पैरामीटर कितना बड़ा या छोटा हो सकता है, कुछ बाधाओं को देखते हुए जिन्हें ग्राफ़ को संतुष्ट करना पड़ता है? ग्राफ़ जो ऐसी अनुकूलन समस्या का इष्टतम समाधान है, उसे एक्सट्रीमल ग्राफ़ कहा जाता है, और एक्सट्रीमल ग्राफ़ एक्सट्रीमल ग्राफ़ सिद्धांत में अध्ययन की महत्वपूर्ण वस्तुएं हैं।

एक्सट्रीमल ग्राफ सिद्धांत रैमसे सिद्धांत, वर्णक्रमीय ग्राफ सिद्धांत, कम्प्यूटेशनल समिष्ट सिद्धांत और एडिटिव कॉम्बिनेटरिक्स जैसे क्षेत्रों से निकटता से संबंधित है, और प्रायः संभाव्य पद्धति को नियोजित करता है।

इतिहास

Extremal graph theory, in its strictest sense, is a branch of graph theory developed and loved by Hungarians.

Bollobás (2004)

मेंटल का प्रमेय (1907) और तुरान का प्रमेय (1941) एक्सट्रीमल ग्राफ सिद्धांत के अध्ययन में प्रथम माइलस्टोन में से कुछ थे। विशेष रूप से, तुरान का प्रमेय अंत में एर्दो-स्टोन प्रमेय (1946) जैसे परिणामों के शोध के लिए प्रेरणा बन गया। यह परिणाम आश्चर्यजनक है क्योंकि यह रंगीन संख्या को किनारों की अधिकतम संख्या से जोड़ता है। $H$-मुक्त ग्राफ़ एर्दो-स्टोन का वैकल्पिक प्रमाण 1975 में दिया गया था, और एक्सट्रीमल ग्राफ सिद्धांत समस्याओं के समाधान में आवश्यक प्रौद्योगिकी, स्ज़ेमेरीडी नियमितता लेम्मा का उपयोग किया गया था।

विषय और अवधारणाएँ

ग्राफ़ रंग

Main article: ग्राफ़ रंग

पीटरसन ग्राफ में वर्णिक संख्या 3 है।

ग्राफ़ का उचित (शीर्ष) रंग $G$ के शीर्षों का रंग है $G$ इस प्रकार कि किसी भी दो आसन्न शीर्षों का रंग एक समान न हो। उचित रूप से रंगने के लिए आवश्यक रंगों की न्यूनतम संख्या $G$ की वर्णिक संख्या कहा जाता है $G$, निरूपित $\chi (G)$ है। विशिष्ट ग्राफ़ की रंगीन संख्या निर्धारित करना एक्सट्रीमल ग्राफ़ सिद्धांत में मौलिक प्रश्न है, क्योंकि क्षेत्र और संबंधित क्षेत्रों में कई समस्याएं ग्राफ़ रंग के संदर्भ में प्रस्तुत की जा सकती हैं।

ग्राफ़ की रंगीन संख्या की दो सरल निचली सीमाएँ $G$ को क्लिक संख्या द्वारा दिया गया है $\omega (G)$-समूह के सभी शीर्षों में भिन्न-भिन्न रंग होने चाहिए-और इसके द्वारा $|V(G)|/\alpha (G)$, जहाँ $\alpha (G)$ स्वतंत्रता संख्या है, क्योंकि किसी दिए गए रंग के साथ शीर्षों के समूह को स्वतंत्र समूह बनाना होगा।

लुब्ध रंग ऊपरी सीमा $\chi (G)\leq \Delta (G)+1$ देता है, जहाँ $\Delta (G)$ की अधिकतम डिग्री $G$ है। जब $G$ यह कोई विषम चक्र या समूह नहीं है, ब्रूक्स प्रमेय कहता है कि ऊपरी सीमा $\Delta (G)$ को कम किया जा सकता है। तब $G$ समतलीय ग्राफ है, चार-रंग प्रमेय यह बताता है कि $G$ इसकी वर्णिक संख्या अधिकतम चार है।

सामान्यतः, यह निर्धारित करना कि किसी दिए गए ग्राफ़ में रंगों की निर्धारित संख्या के साथ रंग है या नहीं है, एनपी-हार्ड के रूप में जाना जाता है।

शीर्ष रंग के अतिरिक्त, अन्य प्रकार के रंग का भी अध्ययन किया जाता है, जैसे किनारे का रंग। रंगीन सूचकांक $\chi '(G)$ ग्राफ का $G$ ग्राफ़ के उचित किनारे-रंग में रंगों की न्यूनतम संख्या है, और विज़िंग के प्रमेय में कहा गया है कि ग्राफ़ का रंगीन सूचकांक $G$ भी है $\Delta (G)$ या $\Delta (G)+1$ भी होता है।

निषिद्ध उपग्राफ

Main article: निषिद्ध उपग्राफ समस्या

निषिद्ध उपग्राफ समस्या एक्सट्रीमल ग्राफ सिद्धांत में केंद्रीय समस्याओं में से है। ग्राफ $G$ दिया गया है, निषिद्ध उपग्राफ समस्या किनारों की अधिकतम संख्या मांगती है $\operatorname {ex} (n,G)$ में $n$-वर्टेक्स ग्राफ़ जिसमें उपग्राफ आइसोमोर्फिक $G$ सम्मिलित नहीं है।

जब $G=K_{r}$ संपूर्ण ग्राफ़ है, तुरान का प्रमेय इसका त्रुटिहीन मान देता है $\operatorname {ex} (n,K_{r})$ और इस अधिकतम को प्राप्त करने वाले सभी ग्राफ़ को चित्रित करता है; ऐसे ग्राफ़ को तुरान ग्राफ़ के रूप में जाना जाता है। गैर-द्विपक्षीय ग्राफ़ के लिए $G$, एर्दो-स्टोन प्रमेय स्पर्शोन्मुख $\operatorname {ex} (n,G)$ की वर्णिक संख्या के संदर्भ में $G$ मूल्य देता है। $\operatorname {ex} (n,G)$ के स्पर्शोन्मुखता का निर्धारण करने की समस्या जब $G$ द्विदलीय ग्राफ विवृत है; तब $G$ यह पूर्ण द्विदलीय ग्राफ है, इसे ज़ारांकिविज़ समस्या के रूप में जाना जाता है।

समरूपता घनत्व

Main article: समरूपता घनत्व

समरूपता घनत्व $t(H,G)$ ग्राफ का $H$ ग्राफ में $G$ इस संभावना का वर्णन करता है कि शीर्ष समूह से यादृच्छिक रूप से चयन किया गया मानचित्र $H$ के शीर्ष समूह के लिए $G$ भी ग्राफ समरूपता है। यह उपग्राफ़ घनत्व से निकटता से संबंधित है, जो बताता है कि ग्राफ़ कितनी बार होता है $H$ के उपसमूह को $G$ के रूप में पाया जाता है।

निषिद्ध सबग्राफ़ समस्या को ग्राफ़ के किनारे घनत्व को अधिकतम करने के रूप में पुनर्स्थापित किया जा सकता है $G$-घनत्व शून्य, और यह स्वाभाविक रूप से ग्राफ समरूपता असमानताओं के रूप में सामान्यीकरण की ओर ले जाता है, जो संबंधित असमानताएं हैं $t(H,G)$ विभिन्न ग्राफ़ के लिए $H$ है। समरूपता घनत्व को ग्राफॉन तक विस्तारित करके, जो ऑब्जेक्ट हैं जो घने ग्राफ की सीमा के रूप में उत्पन्न होते हैं, ग्राफ समरूपता घनत्व को अभिन्न के रूप में लिखा जा सकता है, और कॉची-श्वार्ज़ असमानता और होल्डर की असमानता जैसी समरूपता असमानताओं को प्राप्त करने के लिए उपयोग किया जा सकता है।

समरूपता घनत्व से संबंधित प्रमुख विवृत समस्या सिडोरेंको का अनुमान है, जो ग्राफ में द्विदलीय ग्राफ के समरूपता घनत्व पर सख्त निचली सीमा बताता है। $G$ के किनारे घनत्व के संदर्भ में $G$ होता है।

ग्राफ़ नियमितता

Main article: ज़ेमेरेडी नियमितता लेम्मा

नियमित विभाजन में भागों के मध्य के किनारे उचित रूप से व्यवहार करते हैं।

ज़ेमेरेडी की नियमितता लेम्मा बताती है कि सभी ग्राफ़ निम्नलिखित अर्थों में 'नियमित' हैं: किसी भी दिए गए ग्राफ़ के शीर्ष समूह को भागों की सीमित संख्या में विभाजित किया जा सकता है, जिससे भागों के अधिकांश जोड़े के मध्य का द्विदलीय ग्राफ़ यादृच्छिक द्विदलीय ग्राफ़ के समान व्यवहार करता है। यह विभाजन मूल ग्राफ़ को संरचनात्मक सन्निकटन देता है, जो मूल ग्राफ़ के गुणों के सम्बन्ध में सूचना प्रकट करता है।

नियमितता लेम्मा चरम ग्राफ सिद्धांत में केंद्रीय परिणाम है, और एडिटिव कॉम्बिनेटरिक्स और कम्प्यूटेशनल समिष्ट सिद्धांत के आसन्न क्षेत्रों में भी इसके कई अनुप्रयोग हैं। (सेमेरेडी) नियमितता के अतिरिक्त , ग्राफ़ नियमितता की निकट संबंधी धारणाओं जैसे कि स्थिर नियमितता और फ़्रीज़-कन्नन कमजोर नियमितता का भी अध्ययन किया गया है, साथ ही हाइपरग्राफ में नियमितता के विस्तार का भी अध्ययन किया गया है।

ग्राफ़ नियमितता के अनुप्रयोग प्रायः गणना वाले लेम्मा और विस्थापन वाले लेम्मा के रूपों का उपयोग करते हैं। सरलतम रूपों में, ग्राफ गणना लेम्मा, उपग्राफ की संख्या का अनुमान लगाने के लिए नियमित विभाजन में भागों के जोड़े के मध्य नियमितता का उपयोग करता है, और ग्राफ विस्थापन वाला लेम्मा बताता है कि किसी दिए गए उपग्राफ की कुछ प्रतियों के साथ ग्राफ दिया गया है, हम विस्थापित कर सकते हैं उपग्राफ की सभी प्रतियों को विस्थापित करने के लिए किनारों की छोटी संख्या है।

यह भी देखें

संबंधित क्षेत्रों

• रैमसे सिद्धांत
• रैमसे-तुरान सिद्धांत
• वर्णक्रमीय ग्राफ सिद्धांत
• एडिटिव कॉम्बिनेटरिक्स
• कम्प्यूटेशनल समिष्ट सिद्धांत
• संभाव्य कॉम्बिनेटरिक्स

प्रौद्योगिकी और विधि

• संभाव्य विधि
• आश्रित यादृच्छिक विकल्प
• कंटेनर विधि
• हाइपरग्राफ नियमितता विधि

प्रमेय और अनुमान (ऊपर उल्लिखित प्रमेय के अतिरिक्त )

• अयस्क प्रमेय
• रुज़सा-ज़ेमेरेडी समस्या