चरम ग्राफ़ सिद्धांत

चरम ग्राफ़ सिद्धांत यह पूछता है कि एक निर्धारित उपसंरचना से बचते हुए एक ग्राफ़ कितना बड़ा या सघन हो सकता है, और चरम विन्यासों की पहचान करता है।

Definition

एक ग्राफ़ पैरामीटर के अधिकतम या न्यूनतम मान का अध्ययन, जैसे कि किनारों की संख्या, एक संरचनात्मक बाधा के अधीन जैसे कि एक निश्चित उपग्राफ़ की अनुपस्थिति।

Scope

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

Core questions

• n शीर्षों वाले ग्राफ़ में किनारों की अधिकतम संख्या क्या है जिसमें किसी दिए गए उपग्राफ़ की कोई प्रतिलिपि नहीं है?
• कौन से ग्राफ़ इन चरम सीमाओं को प्राप्त करते हैं?
• एक निषिद्ध उपग्राफ़ की वर्णिक संख्या स्पर्शोन्मुख उत्तर को कैसे नियंत्रित करती है?
• नियमितता विधियाँ सघन ग्राफ़ को परिबद्ध संरचना में कैसे कम करती हैं?

Key concepts

• निषिद्ध उपग्राफ़
• तुरान ग्राफ़
• मेंटल का प्रमेय
• चरम संख्या (तुरान संख्या)
• एर्दोस-स्टोन प्रमेय
• स्ज़ेमेरेडी नियमितता लेम्मा

Key theories

तुरान का प्रमेय

n शीर्षों वाले सभी ग्राफ़ों में, जिनमें r+1 शीर्षों पर कोई पूर्ण उपग्राफ़ नहीं है, संतुलित पूर्ण r-पार्टाइट ग्राफ़ में सबसे अधिक किनारे होते हैं, जो मेंटल के त्रिभुज-मुक्त बंधन को सामान्यीकृत करता है और चरम ग्राफ़ सिद्धांत को आधार प्रदान करता है।

एर्दोस-स्टोन प्रमेय

किसी भी निश्चित निषिद्ध उपग्राफ़ H के लिए, H-मुक्त ग्राफ़ का अधिकतम किनारा घनत्व H की वर्णिक संख्या द्वारा स्पर्शोन्मुख रूप से निर्धारित होता है, जो तुरान-प्रकार के चरम परिणामों को एकीकृत करता है।

Clinical relevance

चरम घनत्व परिणाम बड़े नेटवर्क और बाधा प्रणालियों की संरचना को सीमित करते हैं, और इस क्षेत्र के भीतर विकसित नियमितता विधि के अनुप्रयोग संपत्ति परीक्षण, सैद्धांतिक कंप्यूटर विज्ञान और योगात्मक संयोजनों में हैं।

History

मेंटल का 1907 का त्रिभुज-मुक्त बंधन और तुरान का 1941 का सामान्यीकरण इस क्षेत्र को लॉन्च किया; एर्दोस-स्टोन-सिमोनोविट्स सिद्धांत और स्ज़ेमेरेडी के नियमितता लेम्मा ने इसे आधुनिक संयोजनों का एक केंद्रीय स्तंभ बना दिया।

Key figures

• Paul Turan
• Paul Erdos
• Endre Szemeredi

Seminal works

• bollobas1998
• diestel2017

Frequently asked questions

तुरान-प्रकार की समस्या क्या है?

यह पूछता है कि एक ग्राफ़ में कितने किनारे हो सकते हैं जबकि एक निश्चित उपग्राफ़ से बचा जा सके; इसका प्रामाणिक उदाहरण त्रिभुज-मुक्त ग्राफ़ में अधिकतम किनारे हैं।

चरम ग्राफ़ सिद्धांत रामसे सिद्धांत से कैसे संबंधित है?

दोनों अपरिहार्य संरचना का अध्ययन करते हैं, लेकिन चरम सिद्धांत एक निषिद्ध उपग्राफ़ को ठीक करता है और किनारों को अधिकतम करता है, जबकि रामसे सिद्धांत एक मोनोक्रोमैटिक संरचना की गारंटी देता है जब ग्राफ़ पर्याप्त बड़ा हो जाता है।