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

Latest revision as of 15:49, 2 August 2023

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

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

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

इतिहास

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

Bollobás (2004) ^[3]

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

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

ग्राफ़ रंग

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

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

ग्राफ़ की रंगीन संख्या की दो सरल निचली सीमाएँ $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$ भी होता है।

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

निषिद्ध उपग्राफ समस्या एक्सट्रीमल ग्राफ सिद्धांत में केंद्रीय समस्याओं में से है। ग्राफ $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$ यह पूर्ण द्विदलीय ग्राफ है, इसे ज़ारांकिविज़ समस्या के रूप में जाना जाता है।

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

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

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

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

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

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

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

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

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

यह भी देखें

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

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

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

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

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

संदर्भ

↑ ^1.0 ^1.1 Diestel, Reinhard (2010), Graph Theory (4th ed.), Berlin, New York: Springer-Verlag, pp. 169–198, ISBN 978-3-642-14278-9, archived from the original on 2017-05-28, retrieved 2013-11-18
↑ ^2.0 ^2.1 ^2.2 Alon, Noga; Krivelevich, Michael (2008). "Extremal and Probabilistic Combinatorics". In Gowers, Timothy; Barrow-Green, June; Leader, Imre (eds.). The Princeton Companion to Mathematics (in English). Princeton, New Jersey: Princeton University Press. pp. 562–575. doi:10.1515/9781400830398. ISBN 978-0-691-11880-2. JSTOR j.ctt7sd01. LCCN 2008020450. MR 2467561. OCLC 227205932. OL 19327100M. Zbl 1242.00016.
↑ Bollobás, Béla (2004), Extremal Graph Theory, New York: Dover Publications, ISBN 978-0-486-43596-1
↑ ^4.0 ^4.1 Bollobás, Béla (1998), Modern Graph Theory, Berlin, New York: Springer-Verlag, pp. 103–144, ISBN 978-0-387-98491-9

[:0-1] 1.0 ^1.1 Diestel, Reinhard (2010), Graph Theory (4th ed.), Berlin, New York: Springer-Verlag, pp. 169–198, ISBN 978-3-642-14278-9, archived from the original on 2017-05-28, retrieved 2013-11-18

[pcm-2] 2.0 ^2.1 ^2.2 Alon, Noga; Krivelevich, Michael (2008). "Extremal and Probabilistic Combinatorics". In Gowers, Timothy; Barrow-Green, June; Leader, Imre (eds.). The Princeton Companion to Mathematics (in English). Princeton, New Jersey: Princeton University Press. pp. 562–575. doi:10.1515/9781400830398. ISBN 978-0-691-11880-2. JSTOR j.ctt7sd01. LCCN 2008020450. MR 2467561. OCLC 227205932. OL 19327100M. Zbl 1242.00016.

[3] Bollobás, Béla (2004), Extremal Graph Theory, New York: Dover Publications, ISBN 978-0-486-43596-1

[b104-4] 4.0 ^4.1 Bollobás, Béla (1998), Modern Graph Theory, Berlin, New York: Springer-Verlag, pp. 103–144, ISBN 978-0-387-98491-9

[1]

[2]

[3]

[4]

@@ Line 1: / Line 1: @@
-[[File:Turan 13-4.svg|thumb|तुरान ग्राफ टी(एन,आर) एक चरम ग्राफ का एक उदाहरण है। इसमें (r + 1)-क्लिक (ग्राफ़ सिद्धांत) के बिना n शीर्षों पर एक ग्राफ़ के लिए किनारों की अधिकतम संभव संख्या है। यह टी(13,4) है।]]एक्सट्रीमल [[ग्राफ सिद्धांत]] [[साहचर्य]] की एक शाखा है, जो स्वयं गणित का एक क्षेत्र है, जो [[चरम कॉम्बिनेटरिक्स]] और ग्राफ सिद्धांत के चौराहे पर स्थित है। संक्षेप में, चरम ग्राफ़ सिद्धांत अध्ययन करता है कि ग्राफ़ के वैश्विक गुण स्थानीय उपसंरचना को कैसे प्रभावित करते हैं।
+[[File:Turan 13-4.svg|thumb|तुरान ग्राफ T(n,r) एक्सट्रीमल ग्राफ का उदाहरण है। इसमें (r + 1)-क्लिक (ग्राफ़ सिद्धांत) के बिना n शीर्षों पर ग्राफ़ के लिए किनारों की अधिकतम संभव संख्या है। यह T(13,4) है।]]'''एक्सट्रीमल [[ग्राफ सिद्धांत]]''' [[साहचर्य]] की शाखा है, जो स्वयं गणित का क्षेत्र है, जो [[चरम कॉम्बिनेटरिक्स|एक्सट्रीमल कॉम्बिनेटरिक्स]] और ग्राफ सिद्धांत के अन्तः खंड पर स्थित है। संक्षेप में, एक्सट्रीमल ग्राफ़ सिद्धांत अध्ययन करता है कि ग्राफ़ के वैश्विक गुण स्थानीय उपसंरचना को कैसे प्रभावित करते हैं।<ref name=":0">
-<ref name=":0">
 {{Citation | last1=Diestel | first1=Reinhard | title=Graph Theory | url=http://diestel-graph-theory.com/index.html/ | publisher=Springer-Verlag | location=Berlin, New York | edition=4th | isbn=978-3-642-14278-9 | year=2010 | pages=169–198 | access-date=2013-11-18 | archive-url=https://web.archive.org/web/20170528023122/http://diestel-graph-theory.com/index.html | archive-date=2017-05-28 | url-status=dead }}
-</ref>
+</ref> एक्सट्रीमल ग्राफ़ सिद्धांत में परिणाम विभिन्न [[ग्राफ़ संपत्ति|ग्राफ़ गुणों]] के मध्य मात्रात्मक कनेक्शन से सम्बंधित हैं, दोनों वैश्विक (जैसे कोने और किनारों की संख्या) और स्थानीय (जैसे विशिष्ट उपग्राफों का अस्तित्व), और एक्सट्रीमल ग्राफ़ सिद्धांत में समस्याओं को प्रायःअनुकूलन के रूप में प्रस्तुत किया जा सकता है समस्याएँ: ग्राफ़ का पैरामीटर कितना बड़ा या छोटा हो सकता है, कुछ बाधाओं को देखते हुए जिन्हें ग्राफ़ को संतुष्ट करना पड़ता है?<ref name="pcm">
-चरम ग्राफ़ सिद्धांत में परिणाम विभिन्न [[ग्राफ़ संपत्ति]] के बीच मात्रात्मक कनेक्शन से निपटते हैं, दोनों वैश्विक (जैसे कोने और किनारों की संख्या) और स्थानीय (जैसे विशिष्ट उपग्राफों का अस्तित्व), और चरम ग्राफ़ सिद्धांत में समस्याओं को अक्सर अनुकूलन के रूप में तैयार किया जा सकता है समस्याएँ: ग्राफ़ का एक पैरामीटर कितना बड़ा या छोटा हो सकता है, कुछ बाधाओं को देखते हुए जिन्हें ग्राफ़ को संतुष्ट करना पड़ता है?
-<ref name="pcm" >
 {{Princeton Companion to Mathematics
    |article=Extremal and Probabilistic Combinatorics
@@ Line 15: / Line 12: @@
    |author2-link=Michael Krivelevich
 }}
-</ref>
+</ref> ग्राफ़ जो ऐसी अनुकूलन समस्या का इष्टतम समाधान है, उसे एक्सट्रीमल ग्राफ़ कहा जाता है, और '''एक्सट्रीमल ग्राफ़''' एक्सट्रीमल ग्राफ़ सिद्धांत में अध्ययन की महत्वपूर्ण वस्तुएं हैं।
-एक ग्राफ़ जो ऐसी अनुकूलन समस्या का इष्टतम समाधान है, उसे चरम ग्राफ़ कहा जाता है, और चरम ग्राफ़ चरम ग्राफ़ सिद्धांत में अध्ययन की महत्वपूर्ण वस्तुएं हैं।
-एक्सट्रीमल ग्राफ सिद्धांत [[रैमसे सिद्धांत]], [[वर्णक्रमीय ग्राफ सिद्धांत]], [[कम्प्यूटेशनल जटिलता सिद्धांत]] और [[एडिटिव कॉम्बिनेटरिक्स]] जैसे क्षेत्रों से निकटता से संबंधित है, और अक्सर संभाव्य पद्धति को नियोजित करता है।
+एक्सट्रीमल ग्राफ सिद्धांत [[रैमसे सिद्धांत]], [[वर्णक्रमीय ग्राफ सिद्धांत]], [[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल समिष्ट सिद्धांत]] और [[एडिटिव कॉम्बिनेटरिक्स]] जैसे क्षेत्रों से निकटता से संबंधित है, और प्रायः संभाव्य पद्धति को नियोजित करता है।
 ==इतिहास==
@@ Line 29: / Line 25: @@
 |width=300px}}
-मेंटल का प्रमेय (1907) और तुरान का प्रमेय|तुरान का प्रमेय (1941) चरम ग्राफ सिद्धांत के अध्ययन में पहले मील के पत्थर में से कुछ थे।
+मेंटल का प्रमेय (1907) और तुरान का प्रमेय (1941) एक्सट्रीमल ग्राफ सिद्धांत के अध्ययन में प्रथम माइलस्टोन में से कुछ थे।<ref name="b104">
-<ref name="b104">
 {{Citation | last1=Bollobás | first1=Béla | author1-link=Béla Bollobás | title=Modern Graph Theory | publisher=[[Springer-Verlag]] | location=Berlin, New York | isbn=978-0-387-98491-9 | year=1998 | pages=103–144}}
-</ref> विशेष रूप से, तुरान का प्रमेय बाद में एर्दो-स्टोन प्रमेय (1946) जैसे परिणामों की खोज के लिए प्रेरणा बन गया।<ref name=":0" />यह परिणाम आश्चर्यजनक है क्योंकि यह रंगीन संख्या को किनारों की अधिकतम संख्या से जोड़ता है <math>H</math>-मुक्त ग्राफ़. एर्दो-स्टोन का एक वैकल्पिक प्रमाण 1975 में दिया गया था, और चरम ग्राफ सिद्धांत समस्याओं के समाधान में एक आवश्यक तकनीक, स्ज़ेमेरीडी नियमितता लेम्मा का उपयोग किया गया था।<ref name="b104" />
+</ref> विशेष रूप से, तुरान का प्रमेय अंत में एर्दो-स्टोन प्रमेय (1946) जैसे परिणामों के शोध के लिए प्रेरणा बन गया।<ref name=":0" /> यह परिणाम आश्चर्यजनक है क्योंकि यह रंगीन संख्या को किनारों की अधिकतम संख्या से जोड़ता है। <math>H</math>-मुक्त ग्राफ़ एर्दो-स्टोन का वैकल्पिक प्रमाण 1975 में दिया गया था, और एक्सट्रीमल ग्राफ सिद्धांत समस्याओं के समाधान में आवश्यक प्रौद्योगिकी, स्ज़ेमेरीडी नियमितता लेम्मा का उपयोग किया गया था।<ref name="b104" />
-{{-}}
 ==विषय और अवधारणाएँ==
 ===ग्राफ़ रंग===
-{{main|Graph coloring}}
+{{main|ग्राफ़ रंग}}
-[[File:Petersen graph 3-coloring.svg|thumb|right|[[पीटरसन ग्राफ]] में वर्णिक संख्या 3 है।]]ग्राफ़ का उचित (शीर्ष) रंग <math>G</math> के शीर्षों का एक रंग है <math>G</math> इस प्रकार कि किसी भी दो आसन्न शीर्षों का रंग एक जैसा न हो। उचित रूप से रंगने के लिए आवश्यक रंगों की न्यूनतम संख्या <math>G</math> की वर्णिक संख्या कहलाती है <math>G</math>, निरूपित <math>\chi(G)</math>. विशिष्ट ग्राफ़ की रंगीन संख्या निर्धारित करना चरम ग्राफ़ सिद्धांत में एक मौलिक प्रश्न है, क्योंकि क्षेत्र और संबंधित क्षेत्रों में कई समस्याएं ग्राफ़ रंग के संदर्भ में तैयार की जा सकती हैं।<ref name="pcm" />
+[[File:Petersen graph 3-coloring.svg|thumb|right|[[पीटरसन ग्राफ]] में वर्णिक संख्या 3 है।]]ग्राफ़ का उचित (शीर्ष) रंग <math>G</math> के शीर्षों का रंग है <math>G</math> इस प्रकार कि किसी भी दो आसन्न शीर्षों का रंग एक समान न हो। उचित रूप से रंगने के लिए आवश्यक रंगों की न्यूनतम संख्या <math>G</math> की वर्णिक संख्या कहा जाता है <math>G</math>, निरूपित <math>\chi(G)</math> है। विशिष्ट ग्राफ़ की रंगीन संख्या निर्धारित करना एक्सट्रीमल ग्राफ़ सिद्धांत में मौलिक प्रश्न है, क्योंकि क्षेत्र और संबंधित क्षेत्रों में कई समस्याएं ग्राफ़ रंग के संदर्भ में प्रस्तुत की जा सकती हैं।<ref name="pcm" />
-ग्राफ़ की रंगीन संख्या की दो सरल निचली सीमाएँ <math>G</math> क्लिक संख्या द्वारा दिया गया है <math>\omega(G)</math>-एक समूह के सभी शीर्षों में अलग-अलग रंग होने चाहिए-और इसके द्वारा <math>|V(G)|/\alpha(G)</math>, कहाँ <math>\alpha(G)</math> स्वतंत्रता संख्या है, क्योंकि किसी दिए गए रंग के साथ शीर्षों के सेट को एक [[स्वतंत्र सेट (ग्राफ़ सिद्धांत)]] बनाना होगा।
+ग्राफ़ की रंगीन संख्या की दो सरल निचली सीमाएँ <math>G</math> को क्लिक संख्या द्वारा दिया गया है <math>\omega(G)</math>-समूह के सभी शीर्षों में भिन्न-भिन्न रंग होने चाहिए-और इसके द्वारा <math>|V(G)|/\alpha(G)</math>, जहाँ <math>\alpha(G)</math> स्वतंत्रता संख्या है, क्योंकि किसी दिए गए रंग के साथ शीर्षों के समूह को [[स्वतंत्र सेट (ग्राफ़ सिद्धांत)|स्वतंत्र समूह]] बनाना होगा।
-एक [[लालची रंग]] ऊपरी सीमा देता है <math>\chi(G) \le \Delta(G) + 1</math>, कहाँ <math>\Delta(G)</math> की अधिकतम डिग्री है <math>G</math>. कब <math>G</math> यह कोई अजीब चक्र या गुट नहीं है, ब्रूक्स प्रमेय कहता है कि ऊपरी सीमा को कम किया जा सकता है <math>\Delta(G)</math>. कब <math>G</math> एक [[समतलीय ग्राफ]]़ है, चार-रंग प्रमेय यह बताता है <math>G</math> इसकी वर्णिक संख्या अधिकतम चार है।
+[[लालची रंग|लुब्ध रंग]] ऊपरी सीमा <math>\chi(G) \le \Delta(G) + 1</math> देता है, जहाँ <math>\Delta(G)</math> की अधिकतम डिग्री <math>G</math> है। जब <math>G</math> यह कोई विषम चक्र या समूह नहीं है, ब्रूक्स प्रमेय कहता है कि ऊपरी सीमा <math>\Delta(G)</math> को कम किया जा सकता है। तब <math>G</math> [[समतलीय ग्राफ]] है, चार-रंग प्रमेय यह बताता है कि <math>G</math> इसकी वर्णिक संख्या अधिकतम चार है।
-सामान्य तौर पर, यह निर्धारित करना कि किसी दिए गए ग्राफ़ में रंगों की निर्धारित संख्या के साथ रंग है या नहीं, [[ एनपी कठिन ]] के रूप में जाना जाता है।
+सामान्यतः, यह निर्धारित करना कि किसी दिए गए ग्राफ़ में रंगों की निर्धारित संख्या के साथ रंग है या नहीं है,[[ एनपी कठिन | एनपी-हार्ड]] के रूप में जाना जाता है।
-शीर्ष रंग के अलावा, अन्य प्रकार के रंग का भी अध्ययन किया जाता है, जैसे [[किनारे का रंग]]। रंगीन सूचकांक <math>\chi'(G)</math> एक ग्राफ का <math>G</math> ग्राफ़ के उचित किनारे-रंग में रंगों की न्यूनतम संख्या है, और विज़िंग के प्रमेय में कहा गया है कि ग्राफ़ का रंगीन सूचकांक <math>G</math> भी है <math>\Delta(G)</math> या <math>\Delta(G)+1</math>.
+शीर्ष रंग के अतिरिक्त, अन्य प्रकार के रंग का भी अध्ययन किया जाता है, जैसे [[किनारे का रंग]]। रंगीन सूचकांक <math>\chi'(G)</math> ग्राफ का <math>G</math> ग्राफ़ के उचित किनारे-रंग में रंगों की न्यूनतम संख्या है, और विज़िंग के प्रमेय में कहा गया है कि ग्राफ़ का रंगीन सूचकांक <math>G</math> भी है <math>\Delta(G)</math> या <math>\Delta(G)+1</math> भी होता है।
 ===निषिद्ध उपग्राफ===
-{{main|Forbidden subgraph problem}}
+{{main|निषिद्ध उपग्राफ समस्या}}
-निषिद्ध सबग्राफ समस्या चरम ग्राफ सिद्धांत में केंद्रीय समस्याओं में से एक है। एक ग्राफ दिया गया <math>G</math>, निषिद्ध सबग्राफ समस्या किनारों की अधिकतम संख्या मांगती है <math>\operatorname{ex}(n,G)</math> एक में <math>n</math>-वर्टेक्स ग्राफ़ जिसमें सबग्राफ आइसोमोर्फिक शामिल नहीं है <math>G</math>.
+निषिद्ध उपग्राफ समस्या एक्सट्रीमल ग्राफ सिद्धांत में केंद्रीय समस्याओं में से है। ग्राफ <math>G</math> दिया गया है, निषिद्ध उपग्राफ समस्या किनारों की अधिकतम संख्या मांगती है <math>\operatorname{ex}(n,G)</math> में <math>n</math>-वर्टेक्स ग्राफ़ जिसमें उपग्राफ आइसोमोर्फिक <math>G</math> सम्मिलित नहीं है।
-कब <math>G = K_r</math> एक संपूर्ण ग्राफ़ है, तुरान का प्रमेय इसका सटीक मान देता है <math>\operatorname{ex}(n,K_r)</math> और इस अधिकतम को प्राप्त करने वाले सभी ग्राफ़ को चित्रित करता है; ऐसे ग्राफ़ को तुरान ग्राफ़|तुरान ग्राफ़ के रूप में जाना जाता है।
+जब <math>G = K_r</math> संपूर्ण ग्राफ़ है, तुरान का प्रमेय इसका त्रुटिहीन मान देता है <math>\operatorname{ex}(n,K_r)</math> और इस अधिकतम को प्राप्त करने वाले सभी ग्राफ़ को चित्रित करता है; ऐसे ग्राफ़ को तुरान ग्राफ़ के रूप में जाना जाता है। गैर-द्विपक्षीय ग्राफ़ के लिए <math>G</math>, एर्दो-स्टोन प्रमेय स्पर्शोन्मुख <math>\operatorname{ex}(n, G)</math> की वर्णिक संख्या के संदर्भ में <math>G</math> मूल्य देता है। <math>\operatorname{ex}(n, G)</math> के स्पर्शोन्मुखता का निर्धारण करने की समस्या जब <math>G</math> [[द्विदलीय ग्राफ]] विवृत है; तब <math>G</math> यह पूर्ण द्विदलीय ग्राफ है, इसे [[ज़ारांकिविज़ समस्या]] के रूप में जाना जाता है।
-गैर-द्विपक्षीय ग्राफ़ के लिए <math>G</math>, एर्दो-स्टोन प्रमेय एक स्पर्शोन्मुख मूल्य देता है <math>\operatorname{ex}(n, G)</math> की वर्णिक संख्या के संदर्भ में <math>G</math>.
-के स्पर्शोन्मुखता का निर्धारण करने की समस्या <math>\operatorname{ex}(n, G)</math> कब <math>G</math> एक [[द्विदलीय ग्राफ]] खुला है; कब <math>G</math> यह एक पूर्ण द्विदलीय ग्राफ है, इसे [[ज़ारांकिविज़ समस्या]] के रूप में जाना जाता है।
 ===समरूपता घनत्व===
-{{main|Homomorphism density}}
+{{main|
+समरूपता घनत्व}}
-समरूपता घनत्व <math>t(H, G)</math> एक ग्राफ का <math>H</math> एक ग्राफ में <math>G</math> इस संभावना का वर्णन करता है कि शीर्ष सेट से एक यादृच्छिक रूप से चुना गया नक्शा <math>H</math> के शीर्ष सेट के लिए <math>G</math> यह एक [[ग्राफ समरूपता]] भी है। यह सबग्राफ़ घनत्व से निकटता से संबंधित है, जो बताता है कि एक ग्राफ़ कितनी बार होता है <math>H</math> के उपसमूह के रूप में पाया जाता है <math>G</math>.
+'''समरूपता घनत्व''' <math>t(H, G)</math> ग्राफ का <math>H</math> ग्राफ में <math>G</math> इस संभावना का वर्णन करता है कि शीर्ष समूह से यादृच्छिक रूप से चयन किया गया मानचित्र <math>H</math> के शीर्ष समूह के लिए <math>G</math> भी [[ग्राफ समरूपता]] है। यह '''उपग्राफ़''' '''घनत्व''' से निकटता से संबंधित है, जो बताता है कि ग्राफ़ कितनी बार होता है <math>H</math> के उपसमूह को <math>G</math> के रूप में पाया जाता है।
-निषिद्ध सबग्राफ़ समस्या को ग्राफ़ के किनारे घनत्व को अधिकतम करने के रूप में पुनर्स्थापित किया जा सकता है <math>G</math>-घनत्व शून्य, और यह स्वाभाविक रूप से ग्राफ समरूपता असमानताओं के रूप में सामान्यीकरण की ओर ले जाता है, जो संबंधित असमानताएं हैं <math>t(H, G)</math> विभिन्न ग्राफ़ के लिए <math>H</math>.
+निषिद्ध सबग्राफ़ समस्या को ग्राफ़ के किनारे घनत्व को अधिकतम करने के रूप में पुनर्स्थापित किया जा सकता है <math>G</math>-घनत्व शून्य, और यह स्वाभाविक रूप से '''ग्राफ समरूपता असमानताओं''' के रूप में सामान्यीकरण की ओर ले जाता है, जो संबंधित असमानताएं हैं <math>t(H, G)</math> विभिन्न ग्राफ़ के लिए <math>H</math> है। समरूपता घनत्व को '''ग्राफॉन''' तक विस्तारित करके, जो ऑब्जेक्ट हैं जो घने ग्राफ की सीमा के रूप में उत्पन्न होते हैं, ग्राफ समरूपता घनत्व को अभिन्न के रूप में लिखा जा सकता है, और [[कॉची-श्वार्ज़ असमानता]] और होल्डर की असमानता जैसी समरूपता असमानताओं को प्राप्त करने के लिए उपयोग किया जा सकता है।
-समरूपता घनत्व को ग्राफॉन तक विस्तारित करके, जो कि घने ग्राफ की सीमा के रूप में उत्पन्न होने वाली वस्तुएं हैं, ग्राफ समरूपता घनत्व को अभिन्न के रूप में लिखा जा सकता है, और [[कॉची-श्वार्ज़ असमानता]] और होल्डर की असमानता जैसी असमानताओं को प्राप्त करने के लिए उपयोग किया जा सकता है समरूपता असमानताएँ।
-समरूपता घनत्व से संबंधित एक प्रमुख खुली समस्या सिडोरेंको का अनुमान है, जो एक ग्राफ में द्विदलीय ग्राफ के समरूपता घनत्व पर एक सख्त निचली सीमा बताता है। <math>G</math> के किनारे घनत्व के संदर्भ में <math>G</math>.
+समरूपता घनत्व से संबंधित प्रमुख विवृत समस्या सिडोरेंको का अनुमान है, जो ग्राफ में द्विदलीय ग्राफ के समरूपता घनत्व पर सख्त निचली सीमा बताता है। <math>G</math> के किनारे घनत्व के संदर्भ में <math>G</math> होता है।
 ===ग्राफ़ नियमितता===
-{{main|Szemerédi regularity lemma}}
+{{main|ज़ेमेरेडी नियमितता लेम्मा}}
-[[File:Epsilon regular partition.png|alt=regularity partition|thumb|200x200px|नियमित विभाजन में हिस्सों के बीच के किनारे बेतरतीब ढंग से व्यवहार करते हैं।]]ज़ेमेरेडी की नियमितता लेम्मा बताती है कि सभी ग्राफ़ निम्नलिखित अर्थों में 'नियमित' हैं: किसी भी दिए गए ग्राफ़ के शीर्ष सेट को भागों की एक सीमित संख्या में विभाजित किया जा सकता है, ताकि अधिकांश भागों के जोड़े के बीच द्विदलीय ग्राफ़ [[यादृच्छिक ग्राफ]]़ की तरह व्यवहार करे।<ref name="pcm" />यह विभाजन मूल ग्राफ़ को एक संरचनात्मक सन्निकटन देता है, जो मूल ग्राफ़ के गुणों के बारे में जानकारी प्रकट करता है।
-नियमितता लेम्मा चरम ग्राफ सिद्धांत में एक केंद्रीय परिणाम है, और एडिटिव कॉम्बिनेटरिक्स और कम्प्यूटेशनल जटिलता सिद्धांत के आसन्न क्षेत्रों में भी इसके कई अनुप्रयोग हैं। (सेमेरेडी) नियमितता के अलावा, ग्राफ़ नियमितता की निकट संबंधी धारणाओं जैसे कि मजबूत नियमितता और फ़्रीज़-कन्नन कमजोर नियमितता का भी अध्ययन किया गया है, साथ ही [[हाइपरग्राफ]] में नियमितता के विस्तार का भी अध्ययन किया गया है।
+[[File:Epsilon regular partition.png|alt=regularity partition|thumb|200x200px|नियमित विभाजन में भागों के मध्य के किनारे उचित रूप से व्यवहार करते हैं।]]'''ज़ेमेरेडी की नियमितता लेम्मा''' बताती है कि सभी ग्राफ़ निम्नलिखित अर्थों में 'नियमित' हैं: किसी भी दिए गए ग्राफ़ के शीर्ष समूह को भागों की सीमित संख्या में विभाजित किया जा सकता है, जिससे भागों के अधिकांश जोड़े के मध्य का द्विदलीय ग्राफ़ [[यादृच्छिक ग्राफ|यादृच्छिक द्विदलीय ग्राफ़]] के समान व्यवहार करता है।<ref name="pcm" /> यह विभाजन मूल ग्राफ़ को संरचनात्मक सन्निकटन देता है, जो मूल ग्राफ़ के गुणों के सम्बन्ध में सूचना प्रकट करता है।
-ग्राफ़ नियमितता के अनुप्रयोग अक्सर गिनने वाले लेम्मा और हटाने वाले लेम्मा के रूपों का उपयोग करते हैं। सरलतम रूपों में, ग्राफ हटाने वाला लेम्मा#ग्राफ काउंटिंग लेम्मा, सबग्राफ की संख्या का अनुमान लगाने के लिए एक नियमित विभाजन में भागों के जोड़े के बीच नियमितता का उपयोग करता है, और ग्राफ हटाने वाला लेम्मा बताता है कि किसी दिए गए सबग्राफ की कुछ प्रतियों के साथ एक ग्राफ दिया गया है, हम हटा सकते हैं सबग्राफ की सभी प्रतियों को हटाने के लिए किनारों की एक छोटी संख्या।
+नियमितता लेम्मा चरम ग्राफ सिद्धांत में केंद्रीय परिणाम है, और एडिटिव कॉम्बिनेटरिक्स और कम्प्यूटेशनल समिष्ट सिद्धांत के आसन्न क्षेत्रों में भी इसके कई अनुप्रयोग हैं। (सेमेरेडी) नियमितता के अतिरिक्त , ग्राफ़ नियमितता की निकट संबंधी धारणाओं जैसे कि स्थिर नियमितता और फ़्रीज़-कन्नन कमजोर नियमितता का भी अध्ययन किया गया है, साथ ही [[हाइपरग्राफ]] में नियमितता के विस्तार का भी अध्ययन किया गया है।
-{{-}}
+ग्राफ़ नियमितता के अनुप्रयोग प्रायः गणना वाले लेम्मा और विस्थापन वाले लेम्मा के रूपों का उपयोग करते हैं। सरलतम रूपों में, ग्राफ गणना लेम्मा, उपग्राफ की संख्या का अनुमान लगाने के लिए नियमित विभाजन में भागों के जोड़े के मध्य नियमितता का उपयोग करता है, और ग्राफ विस्थापन वाला लेम्मा बताता है कि किसी दिए गए उपग्राफ की कुछ प्रतियों के साथ ग्राफ दिया गया है, हम विस्थापित कर सकते हैं उपग्राफ की सभी प्रतियों को विस्थापित करने के लिए किनारों की छोटी संख्या है।
 ==यह भी देखें==
@@ Line 87: / Line 76: @@
 * वर्णक्रमीय ग्राफ सिद्धांत
 * एडिटिव कॉम्बिनेटरिक्स
-* कम्प्यूटेशनल जटिलता सिद्धांत
+* कम्प्यूटेशनल समिष्ट सिद्धांत
 * संभाव्य कॉम्बिनेटरिक्स
-तकनीक और तरीके
+प्रौद्योगिकी और विधि
 * संभाव्य विधि
 * [[आश्रित यादृच्छिक विकल्प]]
@@ Line 96: / Line 85: @@
 * [[हाइपरग्राफ नियमितता विधि]]
-प्रमेय और अनुमान (ऊपर उल्लिखित प्रमेय के अलावा)
+प्रमेय और अनुमान (ऊपर उल्लिखित प्रमेय के अतिरिक्त )
 *अयस्क प्रमेय
 * रुज़सा-ज़ेमेरेडी समस्या
@@ Line 102: / Line 91: @@
 ==संदर्भ==
 <references/>
-[[Category: चरम ग्राफ सिद्धांत| चरम ग्राफ सिद्धांत]]
-[[Category: Machine Translated Page]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
+[[Category:CS1 English-language sources (en)]]
 [[Category:Created On 10/07/2023]]
+[[Category:Machine Translated Page]]
+[[Category:Templates Vigyan Ready]]
+[[Category:चरम ग्राफ सिद्धांत| चरम ग्राफ सिद्धांत]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 15:49, 2 August 2023

Contents

इतिहास