ग्राफॉन: Difference between revisions
No edit summary |
No edit summary |
||
| Line 153: | Line 153: | ||
यदि ये संख्याएं हर ग्राफ के करीब हैं <math>F</math>, तब सहज ज्ञान से <math>G</math> और <math>H</math> समान दिखने वाले ग्राफ हैं। | यदि ये संख्याएं हर ग्राफ के करीब हैं <math>F</math>, तब सहज ज्ञान से <math>G</math> और <math>H</math> समान दिखने वाले ग्राफ हैं। | ||
सबग्राफ से सीधे डीलिंग के बजाय, यह ग्राफ समरूपता के साथ काम करने के लिए आसान हो जाता है। | सबग्राफ से सीधे डीलिंग के बजाय, यह ग्राफ समरूपता के साथ काम करने के लिए आसान हो जाता है। | ||
इस परिदृश्य में बृहत्,सघन ग्राफ से डीलिंग के दौरान यह ठीक है | इस परिदृश्य में बृहत्,सघन ग्राफ से डीलिंग के दौरान यह ठीक है, | ||
सबग्राफ की संख्या और एक निश्चित ग्राफ से ग्राफ समरूपता की संख्या असम्बद्ध रूप से बराबर होती है। | सबग्राफ की संख्या और एक निश्चित ग्राफ से ग्राफ समरूपता की संख्या असम्बद्ध रूप से बराबर होती है। | ||
| Line 160: | Line 160: | ||
ग्राफोन समरूपता घनत्व की गणना करने का एक सरल तरीका प्रदान करते हैं। | ग्राफोन समरूपता घनत्व की गणना करने का एक सरल तरीका प्रदान करते हैं। | ||
दरअसल, एक ग्राफ | दरअसल, एक ग्राफ <math>G</math> संबद्ध ग्राफॉन के साथ <math>W_G</math> और दुसरी <math>F</math>, अपने पास है: | ||
<math display=block> t(F, G) = \int \prod_{(i,j)\in E(F)} W_G(x_i, x_j) \; \left\{\mathrm{d}x_i\right\}_{i\in V(F)}</math> | <math display=block> t(F, G) = \int \prod_{(i,j)\in E(F)} W_G(x_i, x_j) \; \left\{\mathrm{d}x_i\right\}_{i\in V(F)}</math> | ||
जहां | जहां अविभाज्य बहुआयामी है, यूनिट अतिविम पर लिया गया है <math>[0,1]^{V(F)}</math>. | ||
यह संबंधित ग्राफॉन की परिभाषा से अनुसरण करता है, जब उपरोक्त | यह संबंधित ग्राफॉन की परिभाषा से अनुसरण करता है, जब उपरोक्त एकीकृत के बराबर होता है <math>1</math>. | ||
फिर हम | फिर हम समरूपता घनत्व की परिभाषा को यादृच्छिक ग्राफॉन <math>W</math> तक बढ़ा सकते हैं, एक ही अभिन्न और परिभाषित करने का उपयोग करके। | ||
<math display=block> t(F, W) = \int \prod_{(i,j)\in E(F)} W(x_i, x_j) \; \left\{\mathrm{d}x_i\right\}_{i\in V(F)}</math> | |||
किसी भी ग्राफ के लिए <math>F</math>. | किसी भी ग्राफ के लिए <math>F</math>. | ||
इस सेटअप को देखते हुए, हम रेखांकन का एक क्रम कहते हैं <math>(G_n)</math> यदि प्रत्येक नियत ग्राफ के लिए | इस सेटअप को देखते हुए, हम रेखांकन का एक क्रम कहते हैं <math>(G_n)</math> यदि प्रत्येक नियत ग्राफ के लिए <math>F</math> वाम-अभिसरण है, समरूपता घनत्व का क्रम <math>\left(t(F, G_n)\right)</math> अभिसरण। | ||
हालांकि अकेले परिभाषा से स्पष्ट नहीं है, अगर <math>(G_n)</math> इस अर्थ में अभिसरण करता है, तो हमेशा एक ग्राफॉन मौजूद होता है <math>W</math> ऐसा है कि हर ग्राफ के लिए <math>F</math>, अपने पास | हालांकि अकेले परिभाषा से स्पष्ट नहीं है, अगर <math>(G_n)</math> इस अर्थ में अभिसरण करता है, तो हमेशा एक ग्राफॉन मौजूद होता है <math>W</math> ऐसा है कि हर ग्राफ के लिए <math>F</math>, अपने पास है: | ||
<math display = "block"> \lim_{n\to\infty} t(F, G_n) = t(F, W) </math> | <math display = "block"> \lim_{n\to\infty} t(F, G_n) = t(F, W) </math> | ||
इसके साथ ही। | इसके साथ ही। | ||
| Line 178: | Line 178: | ||
दो ग्राफ लीजिए <math>G</math> और <math>H</math> उसी शीर्ष सेट पर। | दो ग्राफ लीजिए <math>G</math> और <math>H</math> उसी शीर्ष सेट पर। | ||
क्योंकि ये रेखांकन समान शीर्षों को साझा करते हैं, | क्योंकि ये रेखांकन समान शीर्षों को साझा करते हैं, | ||
उनकी दूरी को मापने का एक तरीका | उनकी दूरी को मापने का एक तरीका <math>X, Y</math> सबसेट तक सीमित करना है वर्टेक्स सेट की, और ऐसे प्रत्येक जोड़ी सबसेट के लिए अश्रि की संख्या की तुलना करें <math>e_G(X,Y)</math> से <math>X</math> को <math>Y</math> में <math>G</math> अश्रि की संख्या के लिए <math>e_H(X,Y)</math> बीच में <math>X</math> और <math>Y</math> में <math>H</math>. | ||
यदि ये संख्याएँ उपसमुच्चयों की प्रत्येक जोड़ी के लिए समान हैं (वर्टेक्स की कुल संख्या के सापेक्ष), तो यह सुझाव देता है <math>G</math> और <math>H</math> समान रेखांकन हैं। | यदि ये संख्याएँ उपसमुच्चयों की प्रत्येक जोड़ी के लिए समान हैं (वर्टेक्स की कुल संख्या के सापेक्ष), तो यह सुझाव देता है <math>G</math> और <math>H</math> समान रेखांकन हैं। | ||
| Line 227: | Line 227: | ||
</ब्लॉककोट> | </ब्लॉककोट> | ||
गिनती लेम्मा नाम उस सीमा से आता है जो यह लेम्मा | गिनती लेम्मा नाम उस सीमा से आता है जो यह लेम्मा समरूपता घनत्व पर देती है <math>t(F, W)</math>, जो ग्राफ़ के सबग्राफ काउंट के अनुरूप हैं। यह लेम्मा Szemerédi_regularity_lemma#Graph_counting_lemma का एक सामान्यीकरण है जो Szemerédi_regularity_lemma के क्षेत्र में दिखाई देता है, और यह तुरंत दिखाता है कि कट दूरी के तहत अभिसरण का अर्थ बाएं-अभिसरण है। | ||
उलटा काउंटिंग लेम्मा। प्रत्येक वास्तविक संख्या के लिए <math>\epsilon > 0</math>, एक वास्तविक संख्या मौजूद है <math>\eta > 0</math> और एक सकारात्मक पूर्णांक <math>k</math> ऐसा कि किसी भी जोड़ी ग्राफोन के लिए <math>U</math> और <math>W</math> साथ | उलटा काउंटिंग लेम्मा। प्रत्येक वास्तविक संख्या के लिए <math>\epsilon > 0</math>, एक वास्तविक संख्या मौजूद है <math>\eta > 0</math> और एक सकारात्मक पूर्णांक <math>k</math> ऐसा कि किसी भी जोड़ी ग्राफोन के लिए <math>U</math> और <math>W</math> साथ | ||
Revision as of 14:47, 18 May 2023
ग्राफ़ सिद्धांत और सांख्यिकी में, एक ग्राफ़ॉन (जिसे ग्राफ़ सीमा के रूप में भी जाना जाता है) एक सममित फलन औसत दर्जे का कार्य है: , जो सघन रेखांकन के अध्ययन में महत्वपूर्ण है। सघन रेखांकन के अनुक्रम की सीमा के लिए ग्राफ़न्स एक प्राकृतिक धारणा के रूप में उत्पन्न होते हैं, और विनिमेय यादृच्छिक चर यादृच्छिक ग्राफ़ मॉडल की मौलिक परिभाषित वस्तुओं के रूप में हैं। ग्राफ़ॉन निम्नलिखित प्रेक्षणों के युग्म द्वारा सघन ग्राफ़ से बंधे हैं: ग्राफ़ॉन द्वारा परिभाषित यादृच्छिक ग्राफ़ मॉडल लगभग निश्चित रूप से सघन ग्राफ़ को वृद्धि देते हैं, और, नियमितता लेम्मा द्वारा, ग्राफ़ॉन यादृच्छिक बृहत् सघन ग्राफ़ की संरचना को प्रग्रहण करते हैं।
सांख्यिकीय सूत्रीकरण
एक ग्राफॉन एक सममित मापने योग्य कार्य है . आमतौर पर एक ग्राफॉन को निम्न योजना के अनुसार विनिमेय यादृच्छिक ग्राफ मॉडल को परिभाषित करने के रूप में समझा जाता है:
- प्रत्येक शीर्ष ग्राफ का एक स्वतंत्र यादृच्छिक मान नियुक्त किया गया है ।
- किनारा संभावना के साथ ग्राफ में स्वतंत्र रूप से शामिल है ।
एक यादृच्छिक ग्राफ मॉडल एक विनिमेय यादृच्छिक ग्राफ मॉडल है और केवल इसे इस तरह (संभवतः यादृच्छिक) ग्राफॉन के संदर्भ में परिभाषित किया जा सकता है। एक निश्चित ग्राफॉन पर अर्द्धरित मॉडल कभी-कभी निरूपित किया जाता है , यादृच्छिक रेखांकन के एर्डोस-रेनी मॉडल के अनुरूप। ग्राफॉन से उत्पन्न ग्राफ इस प्रकार कहा जाता है -यादृच्छिक ग्राफ है।
यह इस परिभाषा और बड़ी संख्या के कानून से चलता है कि, यदि विनिमेय यादृच्छिक ग्राफ मॉडल लगभग निश्चित रूप से सघन हैं।[1]
उदाहरण
ग्राफॉन का सबसे सरल उदाहरण है कुछ स्थिर के लिए . इस मामले में संबंधित विनिमेय यादृच्छिक ग्राफ मॉडल एर्डोस-रेनी मॉडल है जिसमें संभाव्यता के साथ स्वतंत्र रूप से प्रत्येक किनारा शामिल है ।
यदि हम इसके बजाय एक ग्राफ़ॉन के साथ शुरू करते हैं जो टुकड़े वार स्थिर है:
- इकाई वर्ग को विभाजित करना ब्लॉक, और
- सेटिंग के बराबर पर अवरोध पैदा करना,
परिणामी विनिमेय यादृच्छिक ग्राफ मॉडल सामुदायिक स्टोकेस्टिक ब्लॉक मॉडल, एर्डोस-रेनी मॉडल का एक सामान्यीकरण है। हम इसे एक यादृच्छिक ग्राफ मॉडल के रूप में व्याख्या कर सकते हैं मापदंडों के साथ विशिष्ट एर्डोस-रेनी ग्राफ क्रमशः, उनके बीच बिग्राफ के साथ जहां ब्लॉक के बीच प्रत्येक संभावित किनारा और संभाव्यता के साथ स्वतंत्र रूप से शामिल है ।
कई अन्य लोकप्रिय यादृच्छिक ग्राफ़ मॉडल को कुछ ग्राफ़ॉन द्वारा परिभाषित विनिमेय यादृच्छिक ग्राफ़ मॉडल के रूप में समझा जा सकता है, एक विस्तृत सर्वेक्षण ओर्बंज़ और रॉय में शामिल किया गया है।[1]
संयुक्त रूप से विनिमेय आसन्न आव्यूह
आकार का एक यादृच्छिक ग्राफ एक यादृच्छिक सहखंडज आव्यूह के रूप में दर्शाया जा सकता है। विभिन्न आकारों के यादृच्छिक रेखांकन के बीच निरंतरता (प्रोजेक्टिविटी के अर्थ में) लगाने के लिए, ऊपरी-बाएँ n x n उप-आव्यूह के रूप में उत्पन्न होने वाले आसन्न आव्यूह के अनुक्रम का अध्ययन करना स्वाभाविक है। यह हमें उत्पन्न करने की अनुमति देता है एक नोड जोड़कर और अश्रि का नमूना के लिए। इस दृष्टिकोण से, यादृच्छिक रेखांकन को यादृच्छिक अनंत सममित सरणियों के रूप में परिभाषित किया जाता है।
शास्त्रीय संभाव्यता में विनिमेय यादृच्छिक चर के मूलभूत महत्व के बाद, यादृच्छिक ग्राफ सेटिंग में एक समान धारणा की तलाश करना स्वाभाविक है। ऐसी ही एक धारणा संयुक्त रूप से विनिमेय आव्यूह द्वारा दी गई है; यानी यादृच्छिक आव्यूह संतोषजनक है:
सभी क्रमपरिवर्तन के लिए प्राकृतिक संख्याओं की, जहाँ का अर्थ है यादृच्छिक चर#वितरण में समानता। सहज रूप से, इस स्थिति का अर्थ है कि यादृच्छिक ग्राफ का वितरण इसके शीर्षों के लेबलिंग द्वारा अपरिवर्तित है: अर्थात, शीर्षों के लेबल में कोई जानकारी नहीं होती है।
विनिमेय अनुक्रमों के लिए डी फिनेटी के प्रतिनिधित्व प्रमेय के अनुरूप, संयुक्त रूप से विनिमेय यादृच्छिक आसन्न आव्यूह के लिए एक प्रतिनिधित्व प्रमेय है। यह संयुक्त रूप से विनिमेय सरणियों के लिए एल्डस-हूवर प्रमेय का एक विशेष मामला है और इस सेटिंग में, यह दावा करता है कि यादृच्छिक आव्यूह द्वारा उत्पन्न होता है:
- नमूना स्वतंत्र रूप से
- संभावना के साथ यादृच्छिक रूप से स्वतंत्र रूप से
जहाँ एक (संभवतः यादृच्छिक) ग्राफॉन है। यही है, एक यादृच्छिक ग्राफ़ मॉडल में संयुक्त रूप से विनिमेय आसन्न आव्यूह होता है यदि यह केवल कुछ ग्राफ़ॉन के संदर्भ में परिभाषित संयुक्त रूप से विनिमेय यादृच्छिक ग्राफ़ मॉडल है।
ग्राफॉन अनुमान
पहचानने योग्य मुद्दों के कारण, ग्राफॉन फलन का अनुमान लगाना असंभव है, नोड अव्यक्त स्थिति और ग्राफॉन अनुमान की दो मुख्य दिशाएँ हैं। एक दिशा का उद्देश्य अनुमान लगाना है एक समकक्ष वर्ग तक,[2][3] या द्वारा प्रेरित प्रायिकता आव्यूह का अनुमान लगाएं।[4][5]
विश्लेषणात्मक सूत्रीकरण
कोई भी ग्राफ वर्टेक्स इसके आसन्न आव्यूह के साथ पहचाना जा सकता है . यह आव्यूह एक स्टेपफंक्शन से मेल खाता है , विभाजन द्वारा परिभाषित अंतराल में
ऐसा है कि इंटीरियर है
का प्रवेश . यह समारोह ग्राफ का संबद्ध ग्राफॉन से है
सामान्य तौर पर, यदि हमारे पास रेखांकन का एक क्रम है जहां शीर्षों की संख्या अनंत तक जाता है, हम इसका विश्लेषण कर सकते हैं कार्यों के सीमित संचालन पर विचार करके अनुक्रम के संचालन को सीमित करना . यदि ये ग्राफ़ अभिसरित होते हैं (अभिसरण की कुछ उपयुक्त परिभाषा के अनुसार), तो हम उम्मीद करते हैं कि इन ग्राफ़ की सीमा इन संबंधित कार्यों की सीमा के अनुरूप होगी।
यह एक सममित मापने योग्य फलन के रूप में एक ग्राफॉन (ग्राफ़ फलन के लिए छोटा) की परिभाषा को प्रेरित करता है रेखांकन के अनुक्रम की सीमा की धारणा को पकड़ता है। यह पता चला है कि सघन रेखांकन के अनुक्रमों के लिए, अभिसरण की स्पष्ट रूप से भिन्न कई धारणाएँ समतुल्य हैं और उन सभी के अंतर्गत प्राकृतिक सीमा वस्तु एक ग्राफॉन है।[6]
उदाहरण
लगातार ग्राफॉन
एर्डोस-रेनी यादृच्छिक रेखांकन का क्रम लीजिए कुछ निश्चित पैरामीटर के साथ . सहज रूप से, जैसा अनंत की ओर जाता है, रेखांकन के इस क्रम की सीमा पूरी तरह से इन रेखांकन के शीर्ष घनत्व द्वारा निर्धारित की जाती है। ग्राफ़न्स के स्थान में, यह पता चला है कि ऐसा अनुक्रम यादृच्छिक चर के अभिसरण # लगभग_निश्चित_अभिसरण को स्थिरांक में परिवर्तित करता है , जो उपरोक्त अंतर्ज्ञान को प्रग्रहण कर लेता है।
अर्द्ध ग्राफॉन
अर्द्ध ग्राफ का क्रम लीजिए अर्द्ध ग्राफ, लेने से परिभाषित द्विदलीय ग्राफ पर होना वर्टेक्स और ऐसा है कि लगी हुई है ठीक है जब है. यदि शीर्षों को प्रस्तुत क्रम में सूचीबद्ध किया गया है, तब निकटतम आव्यूह अर्द्ध वर्ग ब्लॉक आव्यूह के दो वर्टेक्स पूरित हैं, शेष प्रविष्टियाँ शून्य के बराबर हैं। उदाहरण के लिए, आसन्न आव्यूह द्वारा दिया गया है
पूर्ण द्विदलीय ग्राफॉन
क्रम लीजिए समान आकार के भागों के साथ पूर्ण द्विदलीय ग्राफ का क्रम लीजिए। यदि हम शुरुआत में सभी शीर्षों को एक भाग में रखकर शीर्षों को क्रमित करते हैं और दूसरे भाग के शीर्षों को अंत में रखकर, निकटतम आव्यूह एक ब्लॉक ऑफ-विकर्ण आव्यूह की तरह दिखता है, जिसमें दो ब्लॉक और शून्य के दो ब्लॉक होते हैं। उदाहरण के लिए, आसन्न आव्यूह द्वारा दिया गया है
यदि हम इसके बजाय शीर्षों को आदेश दें भागों के बीच बारी-बारी से, आसन्न आव्यूह में शून्य और एक की शतरंज की संरचना होती है। उदाहरण के लिए, इस आदेश के तहत, आसन्न आव्यूह द्वारा दिया गया है