ग्राफॉन: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 2: | Line 2: | ||
<math>U_{k} \sim \mathrm{U}(0,1)</math> (ऊर्ध्वाधर अक्ष के साथ मान) और | <math>U_{k} \sim \mathrm{U}(0,1)</math> (ऊर्ध्वाधर अक्ष के साथ मान) और | ||
प्रत्येक शीर्ष सहित <math>(k,l)</math> संभावना के साथ स्वतंत्र रूप से <math>f(U_{k},U_{l})</math>. | प्रत्येक शीर्ष सहित <math>(k,l)</math> संभावना के साथ स्वतंत्र रूप से <math>f(U_{k},U_{l})</math>. | ||
उदाहरण के लिए, किनारा <math>(3,5)</math> (हरा, बिंदीदार) संभावना के साथ | उदाहरण के लिए, किनारा <math>(3,5)</math> (हरा, बिंदीदार) संभावना के साथ सम्मलित है | ||
<math>f(0.72,0.9)</math>; दाहिने वर्ग में हरे बक्से का प्रतिनिधित्व करते हैं | <math>f(0.72,0.9)</math>; दाहिने वर्ग में हरे बक्से का प्रतिनिधित्व करते हैं | ||
के मूल्य <math>(u_{3},u_{5})</math> और <math>(u_{5},u_{3})</math>. ऊपरी बाएँ | के मूल्य <math>(u_{3},u_{5})</math> और <math>(u_{5},u_{3})</math>. ऊपरी बाएँ | ||
| Line 9: | Line 9: | ||
== सांख्यिकीय सूत्रीकरण == | == सांख्यिकीय सूत्रीकरण == | ||
एक ग्राफॉन एक सममित मापने योग्य कार्य है <math>W:[0,1]^{2}\to[0,1]</math>. | एक ग्राफॉन एक सममित मापने योग्य कार्य है <math>W:[0,1]^{2}\to[0,1]</math>. सामान्यत: एक ग्राफॉन को निम्न योजना के अनुसार विनिमेय यादृच्छिक ग्राफ मॉडल को परिभाषित करने के रूप में समझा जाता है: | ||
# प्रत्येक शीर्ष <math>j</math> ग्राफ का एक स्वतंत्र यादृच्छिक मान नियुक्त किया गया है <math>u_{j}\sim U[0,1]</math>। | # प्रत्येक शीर्ष <math>j</math> ग्राफ का एक स्वतंत्र यादृच्छिक मान नियुक्त किया गया है <math>u_{j}\sim U[0,1]</math>। | ||
# किनारा <math>(i,j)</math> संभावना के साथ ग्राफ में स्वतंत्र रूप से | # किनारा <math>(i,j)</math> संभावना के साथ ग्राफ में स्वतंत्र रूप से सम्मलित है <math>W(u_{i},u_{j})</math>। | ||
एक यादृच्छिक ग्राफ मॉडल एक विनिमेय यादृच्छिक ग्राफ मॉडल है और केवल इसे इस तरह (संभवतः यादृच्छिक) ग्राफॉन के संदर्भ में परिभाषित किया जा सकता है। | एक यादृच्छिक ग्राफ मॉडल एक विनिमेय यादृच्छिक ग्राफ मॉडल है और केवल इसे इस तरह (संभवतः यादृच्छिक) ग्राफॉन के संदर्भ में परिभाषित किया जा सकता है। | ||
| Line 25: | Line 25: | ||
=== उदाहरण === | === उदाहरण === | ||
ग्राफॉन का सबसे सरल उदाहरण है <math>W(x,y)\equiv p</math> कुछ स्थिर के लिए <math>p\in[0,1]</math>. इस | ग्राफॉन का सबसे सरल उदाहरण है <math>W(x,y)\equiv p</math> कुछ स्थिर के लिए <math>p\in[0,1]</math>. इस स्थितियों में संबंधित विनिमेय यादृच्छिक ग्राफ मॉडल एर्डोस-रेनी मॉडल है <math>G(n,p)</math> जिसमें संभाव्यता के साथ स्वतंत्र रूप से प्रत्येक किनारा सम्मलित है <math>p</math>। | ||
यदि हम इसके | यदि हम इसके अतिरिक्त एक ग्राफ़ॉन के साथ शुरू करते हैं जो टुकड़े वार स्थिर है: | ||
# इकाई वर्ग को विभाजित करना <math>k\times k</math> ब्लॉक, और | # इकाई वर्ग को विभाजित करना <math>k\times k</math> ब्लॉक, और | ||
| Line 33: | Line 33: | ||
परिणामी विनिमेय यादृच्छिक ग्राफ मॉडल <math>k</math> सामुदायिक[[ स्टोकेस्टिक ब्लॉक मॉडल | स्टोकेस्टिक ब्लॉक मॉडल,]] एर्डोस-रेनी मॉडल का एक सामान्यीकरण है। | परिणामी विनिमेय यादृच्छिक ग्राफ मॉडल <math>k</math> सामुदायिक[[ स्टोकेस्टिक ब्लॉक मॉडल | स्टोकेस्टिक ब्लॉक मॉडल,]] एर्डोस-रेनी मॉडल का एक सामान्यीकरण है। | ||
हम इसे एक यादृच्छिक ग्राफ मॉडल के रूप में व्याख्या कर सकते हैं <math>k</math> मापदंडों के साथ विशिष्ट एर्डोस-रेनी ग्राफ <math>p_{ll}</math> क्रमशः, उनके बीच बिग्राफ के साथ जहां ब्लॉक के बीच प्रत्येक संभावित किनारा <math>(l,l)</math> और <math>(m,m)</math> संभाव्यता के साथ स्वतंत्र रूप से | हम इसे एक यादृच्छिक ग्राफ मॉडल के रूप में व्याख्या कर सकते हैं <math>k</math> मापदंडों के साथ विशिष्ट एर्डोस-रेनी ग्राफ <math>p_{ll}</math> क्रमशः, उनके बीच बिग्राफ के साथ जहां ब्लॉक के बीच प्रत्येक संभावित किनारा <math>(l,l)</math> और <math>(m,m)</math> संभाव्यता के साथ स्वतंत्र रूप से सम्मलित है <math>p_{lm}</math>। | ||
कई अन्य लोकप्रिय यादृच्छिक ग्राफ़ मॉडल को कुछ ग्राफ़ॉन द्वारा परिभाषित विनिमेय यादृच्छिक ग्राफ़ मॉडल के रूप में समझा जा सकता है, एक विस्तृत सर्वेक्षण ओर्बंज़ और रॉय में | कई अन्य लोकप्रिय यादृच्छिक ग्राफ़ मॉडल को कुछ ग्राफ़ॉन द्वारा परिभाषित विनिमेय यादृच्छिक ग्राफ़ मॉडल के रूप में समझा जा सकता है, एक विस्तृत सर्वेक्षण ओर्बंज़ और रॉय में सम्मलित किया गया है।<ref name=Orbanz:Roy:2015 /> | ||
| Line 42: | Line 42: | ||
<math>n</math> आकार का एक यादृच्छिक ग्राफ एक यादृच्छिक <math>n\times n</math> सहखंडज आव्यूह के रूप में दर्शाया जा सकता है। विभिन्न आकारों के यादृच्छिक रेखांकन के बीच निरंतरता (प्रोजेक्टिविटी के अर्थ में) लगाने के लिए, ऊपरी-बाएँ ''n'' x ''n'' उप-आव्यूह के रूप में उत्पन्न होने वाले आसन्न आव्यूह के अनुक्रम का अध्ययन करना स्वाभाविक है। यह हमें <math>G_{n}</math> उत्पन्न करने की अनुमति देता है एक <math>G_{n-1}</math> नोड जोड़कर और अश्रि का नमूना <math>(j,n)</math> <math>j<n</math> के लिए। इस दृष्टिकोण से, यादृच्छिक रेखांकन को यादृच्छिक <math>(X_{ij})</math> अनंत सममित सरणियों के रूप में परिभाषित किया जाता है। | <math>n</math> आकार का एक यादृच्छिक ग्राफ एक यादृच्छिक <math>n\times n</math> सहखंडज आव्यूह के रूप में दर्शाया जा सकता है। विभिन्न आकारों के यादृच्छिक रेखांकन के बीच निरंतरता (प्रोजेक्टिविटी के अर्थ में) लगाने के लिए, ऊपरी-बाएँ ''n'' x ''n'' उप-आव्यूह के रूप में उत्पन्न होने वाले आसन्न आव्यूह के अनुक्रम का अध्ययन करना स्वाभाविक है। यह हमें <math>G_{n}</math> उत्पन्न करने की अनुमति देता है एक <math>G_{n-1}</math> नोड जोड़कर और अश्रि का नमूना <math>(j,n)</math> <math>j<n</math> के लिए। इस दृष्टिकोण से, यादृच्छिक रेखांकन को यादृच्छिक <math>(X_{ij})</math> अनंत सममित सरणियों के रूप में परिभाषित किया जाता है। | ||
शास्त्रीय संभाव्यता में विनिमेय यादृच्छिक चर के मूलभूत महत्व के बाद, यादृच्छिक ग्राफ सेटिंग में एक समान धारणा की तलाश करना स्वाभाविक है। ऐसी ही एक धारणा संयुक्त रूप से विनिमेय आव्यूह द्वारा दी गई है; | शास्त्रीय संभाव्यता में विनिमेय यादृच्छिक चर के मूलभूत महत्व के बाद, यादृच्छिक ग्राफ सेटिंग में एक समान धारणा की तलाश करना स्वाभाविक है। ऐसी ही एक धारणा संयुक्त रूप से विनिमेय आव्यूह द्वारा दी गई है; अर्थात यादृच्छिक आव्यूह संतोषजनक है: | ||
: <math> (X_{ij}) \ \overset{d}{=} \, (X_{\sigma(i)\sigma(j)})</math> | : <math> (X_{ij}) \ \overset{d}{=} \, (X_{\sigma(i)\sigma(j)})</math> | ||
सभी क्रमपरिवर्तन के लिए <math>\sigma</math> प्राकृतिक संख्याओं की, जहाँ <math>\overset{d}{=}</math> का अर्थ है यादृच्छिक चर#वितरण में समानता। सहज रूप से, इस स्थिति का अर्थ है कि यादृच्छिक ग्राफ का वितरण इसके शीर्षों के लेबलिंग द्वारा अपरिवर्तित है: अर्थात, शीर्षों के लेबल में कोई जानकारी नहीं होती है। | सभी क्रमपरिवर्तन के लिए <math>\sigma</math> प्राकृतिक संख्याओं की, जहाँ <math>\overset{d}{=}</math> का अर्थ है यादृच्छिक चर#वितरण में समानता। सहज रूप से, इस स्थिति का अर्थ है कि यादृच्छिक ग्राफ का वितरण इसके शीर्षों के लेबलिंग द्वारा अपरिवर्तित है: अर्थात, शीर्षों के लेबल में कोई जानकारी नहीं होती है। | ||
विनिमेय अनुक्रमों के लिए डी फिनेटी के प्रतिनिधित्व प्रमेय के अनुरूप, संयुक्त रूप से विनिमेय यादृच्छिक आसन्न आव्यूह के लिए एक प्रतिनिधित्व प्रमेय है। यह संयुक्त रूप से विनिमेय सरणियों के लिए एल्डस-हूवर प्रमेय का एक विशेष | विनिमेय अनुक्रमों के लिए डी फिनेटी के प्रतिनिधित्व प्रमेय के अनुरूप, संयुक्त रूप से विनिमेय यादृच्छिक आसन्न आव्यूह के लिए एक प्रतिनिधित्व प्रमेय है। यह संयुक्त रूप से विनिमेय सरणियों के लिए एल्डस-हूवर प्रमेय का एक विशेष स्थितिा है और इस सेटिंग में, यह दावा करता है कि यादृच्छिक आव्यूह <math>(X_{ij})</math> द्वारा उत्पन्न होता है: | ||
# नमूना <math>u_{j}\sim U[0,1]</math> स्वतंत्र रूप से | # नमूना <math>u_{j}\sim U[0,1]</math> स्वतंत्र रूप से | ||
| Line 102: | Line 102: | ||
<math display=block> \begin{bmatrix} 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \end{bmatrix}.</math> | <math display=block> \begin{bmatrix} 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \end{bmatrix}.</math> | ||
जैसा <math>n</math> बड़ा हो जाता है, आसन्न आव्यूह की यह ब्लॉक संरचना स्थिर रहती है, | जैसा <math>n</math> बड़ा हो जाता है, आसन्न आव्यूह की यह ब्लॉक संरचना स्थिर रहती है, | ||
जिससे कि रेखांकन का यह क्रम पूर्ण द्विदलीय ग्राफॉन में परिवर्तित हो जाए <math>W</math> | |||
द्वारा परिभाषित <math>W(x,y) = 1</math> जब कभी भी <math>\min(x,y) \le 1/2</math> और <math>\max(x,y) > 1/2</math>, और सेटिंग <math>W(x,y) = 0</math> अन्यथा हो। | द्वारा परिभाषित <math>W(x,y) = 1</math> जब कभी भी <math>\min(x,y) \le 1/2</math> और <math>\max(x,y) > 1/2</math>, और सेटिंग <math>W(x,y) = 0</math> अन्यथा हो। | ||
यदि हम इसके | यदि हम इसके अतिरिक्त शीर्षों को आदेश दें <math>K_{n,n}</math> भागों के बीच बारी-बारी से, | ||
आसन्न आव्यूह में शून्य और एक की शतरंज की संरचना होती है। | आसन्न आव्यूह में शून्य और एक की शतरंज की संरचना होती है। | ||
उदाहरण के लिए, इस आदेश के | उदाहरण के लिए, इस आदेश के अनुसार, आसन्न आव्यूह <math>K_{2,2}</math> द्वारा दिया गया है | ||
<math display=block> \begin{bmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{bmatrix}.</math> जैसा <math>n</math> बड़ा हो जाता है, | <math display=block> \begin{bmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{bmatrix}.</math> जैसा <math>n</math> बड़ा हो जाता है, | ||
| Line 135: | Line 135: | ||
यदि हम मीट्रिक में रुचि रखते हैं जो ग्राफ़ के चरम गुणों को संरक्षित करता है, | यदि हम मीट्रिक में रुचि रखते हैं जो ग्राफ़ के चरम गुणों को संरक्षित करता है, | ||
तो हमें अपना ध्यान उन आव्युह तक सीमित रखना चाहिए जो समान रूप से यादृच्छिक ग्राफ़ की पहचान करते हैं। | तो हमें अपना ध्यान उन आव्युह तक सीमित रखना चाहिए जो समान रूप से यादृच्छिक ग्राफ़ की पहचान करते हैं। | ||
उदाहरण के लिए, यदि हम यादृच्छिक ढंग से एक एर्डोस-रेनी मॉडल से स्वतंत्र रूप से दो ग्राफ़ बनाते हैं <math>G(n,p)</math> कुछ निश्चित के लिए <math>p</math>, एक उचित मीट्रिक के | उदाहरण के लिए, यदि हम यादृच्छिक ढंग से एक एर्डोस-रेनी मॉडल से स्वतंत्र रूप से दो ग्राफ़ बनाते हैं <math>G(n,p)</math> कुछ निश्चित के लिए <math>p</math>, एक उचित मीट्रिक के अनुसार इन दो ग्राफ़ के बीच की दूरी शून्य के करीब होनी चाहिए और बृहत् <math>n</math> के लिए उच्च संभावना है। | ||
स्वाभाविक रूप से, एक ही वर्टेक्स सेट पर दो ग्राफ़ दिए गए हैं, कोई उनकी दूरी को अश्रि की संख्या के रूप में परिभाषित कर सकता है जिसे एक ग्राफ़ से दूसरे ग्राफ़ में प्राप्त करने के लिए जोड़ा या हटाया जाना चाहिए, अर्थात उनका ग्राफ़ एडिट डिस्टेंस है। | स्वाभाविक रूप से, एक ही वर्टेक्स सेट पर दो ग्राफ़ दिए गए हैं, कोई उनकी दूरी को अश्रि की संख्या के रूप में परिभाषित कर सकता है जिसे एक ग्राफ़ से दूसरे ग्राफ़ में प्राप्त करने के लिए जोड़ा या हटाया जाना चाहिए, अर्थात उनका ग्राफ़ एडिट डिस्टेंस है। चूंकि, संपादन दूरी समान रूप से यादृच्छिक ग्राफ़ की पहचान नहीं करती है; वास्तव में, दो रेखांकन स्वतंत्र रूप से खींचे गए हैं <math>G(n,\tfrac{1}{2})</math> की अपेक्षित (सामान्यीकृत) संपादन दूरी है <math>\tfrac{1}{2}</math>. | ||
दो प्राकृतिक आव्युह हैं जो सघन यादृच्छिक ग्राफ़ पर उस अर्थ में अच्छा संचालन करते हैं जो हम चाहते हैं। | दो प्राकृतिक आव्युह हैं जो सघन यादृच्छिक ग्राफ़ पर उस अर्थ में अच्छा संचालन करते हैं जो हम चाहते हैं। | ||
| Line 144: | Line 144: | ||
चमत्कारिक ढंग से, ग्राफ़ का एक क्रम ठीक उसी समय एक मीट्रिक के संबंध में अभिसरण करता है जब यह दूसरे के संबंध में अभिसरण करता है। | चमत्कारिक ढंग से, ग्राफ़ का एक क्रम ठीक उसी समय एक मीट्रिक के संबंध में अभिसरण करता है जब यह दूसरे के संबंध में अभिसरण करता है। | ||
इसके | इसके अतिरिक्त, दोनों आव्युह के अनुसार लिमिट ऑब्जेक्ट ग्राफॉन बन जाते हैं। | ||
अभिसरण की इन दो धारणाओं की समानता यह दर्शाती है कि फैन चुंग अर्ध-यादृच्छिक ग्राफ की विभिन्न धारणाएँ किस प्रकार समतुल्य हैं।{{r|qrandom}} | अभिसरण की इन दो धारणाओं की समानता यह दर्शाती है कि फैन चुंग अर्ध-यादृच्छिक ग्राफ की विभिन्न धारणाएँ किस प्रकार समतुल्य हैं।{{r|qrandom}} | ||
| Line 150: | Line 150: | ||
दो रेखांकन के बीच की दूरी को मापने का एक तरीका <math>G</math> और <math>H</math> के सापेक्ष सबग्राफ गणनांक की तुलना करना है। | दो रेखांकन के बीच की दूरी को मापने का एक तरीका <math>G</math> और <math>H</math> के सापेक्ष सबग्राफ गणनांक की तुलना करना है। | ||
अर्थात प्रत्येक ग्राफ के लिए हम <math>F</math> की प्रतियों की संख्या की तुलना कर सकते हैं <math>F</math> में <math>G</math> और <math>F</math> में <math>H</math>। | |||
यदि ये संख्याएं हर ग्राफ के करीब हैं <math>F</math>, तब सहज ज्ञान से <math>G</math> और <math>H</math> समान दिखने वाले ग्राफ हैं। | यदि ये संख्याएं हर ग्राफ के करीब हैं <math>F</math>, तब सहज ज्ञान से <math>G</math> और <math>H</math> समान दिखने वाले ग्राफ हैं। | ||
सबग्राफ से सीधे डीलिंग के | सबग्राफ से सीधे डीलिंग के अतिरिक्त, यह ग्राफ समरूपता के साथ काम करने के लिए आसान हो जाता है। | ||
इस परिदृश्य में बृहत्,सघन ग्राफ से डीलिंग के दौरान यह ठीक है, | इस परिदृश्य में बृहत्,सघन ग्राफ से डीलिंग के दौरान यह ठीक है, | ||
सबग्राफ की संख्या और एक निश्चित ग्राफ से ग्राफ समरूपता की संख्या असम्बद्ध रूप से बराबर होती है। | सबग्राफ की संख्या और एक निश्चित ग्राफ से ग्राफ समरूपता की संख्या असम्बद्ध रूप से बराबर होती है। | ||
| Line 171: | Line 171: | ||
इस सेटअप को देखते हुए, हम रेखांकन का एक क्रम कहते हैं <math>(G_n)</math> यदि प्रत्येक नियत ग्राफ के लिए <math>F</math> वाम-अभिसरण है, समरूपता घनत्व का क्रम <math>\left(t(F, G_n)\right)</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 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 208: | Line 208: | ||
दो ग्राफ़ के बीच कट की दूरी को उनके संबंधित ग्राफ़ॉन के बीच कट की दूरी के रूप में परिभाषित किया गया है। | दो ग्राफ़ के बीच कट की दूरी को उनके संबंधित ग्राफ़ॉन के बीच कट की दूरी के रूप में परिभाषित किया गया है। | ||
अब हम कहते हैं कि रेखांकन का एक क्रम <math>(G_n)</math> कट दूरी के | अब हम कहते हैं कि रेखांकन का एक क्रम <math>(G_n)</math> कट दूरी के अनुसार अभिसारी है यदि यह कट दूरी के अनुसार एक कॉची अनुक्रम है <math>\delta_\square</math>. चूंकि यह परिभाषा का सीधा परिणाम नहीं है, यदि ग्राफ का ऐसा क्रम कॉची है, तो <math>W</math> हमेशा किसी ग्राफॉन में परिवर्तित हो जाता है। | ||
[[Category:Articles with hatnote templates targeting a nonexistent page]] | [[Category:Articles with hatnote templates targeting a nonexistent page]] | ||
| Line 219: | Line 219: | ||
==== अभिसरण की समानता ==== | ==== अभिसरण की समानता ==== | ||
जैसे ही यह पता चला कि रेखांकन के किसी भी क्रम के लिए <math>(G_n)</math>, बायाँ-अभिसरण कट दूरी के | जैसे ही यह पता चला कि रेखांकन के किसी भी क्रम के लिए <math>(G_n)</math>, बायाँ-अभिसरण कट दूरी के अनुसार अभिसरण के बराबर है, और इसके अतिरिक्त, सीमा रेखाचित्र <math>W</math> एक ही है। हम समान परिभाषाओं का उपयोग करके स्वयं ग्राफोन के अभिसरण पर भी विचार कर सकते हैं, और समान समानता सत्य है। वास्तव में, अभिसरण की दोनों धारणाएं काउंटिंग लेम्मा के माध्यम से अधिक मजबूती से संबंधित हैं।{{r|Lovasz:2013}} | ||
<ब्लॉककोट>काउंटिंग लेम्मा। ग्राफॉन की किसी भी जोड़ी के लिए <math>U</math> और <math>W</math>, अपने पास है: | <ब्लॉककोट>काउंटिंग लेम्मा। ग्राफॉन की किसी भी जोड़ी के लिए <math>U</math> और <math>W</math>, अपने पास है: | ||
| Line 226: | Line 226: | ||
</ब्लॉककोट> | </ब्लॉककोट> | ||
गिनती लेम्मा नाम उस सीमा से आता है जो यह लेम्मा समरूपता घनत्व पर देती है <math>t(F, W)</math>, जो ग्राफ़ के सबग्राफ काउंट के अनुरूप हैं। यह लेम्मा ज़ेमेरेडी नियमितता लेम्मा# ग्राफ काउंटिंग लेम्मा का एक सामान्यीकरण है जो ज़ेमेरेडी नियमितता लेम्मा के क्षेत्र में दिखाई देता है, और यह तुरंत दिखाता है कि कट दूरी के | गिनती लेम्मा नाम उस सीमा से आता है जो यह लेम्मा समरूपता घनत्व पर देती है <math>t(F, W)</math>, जो ग्राफ़ के सबग्राफ काउंट के अनुरूप हैं। यह लेम्मा ज़ेमेरेडी नियमितता लेम्मा# ग्राफ काउंटिंग लेम्मा का एक सामान्यीकरण है जो ज़ेमेरेडी नियमितता लेम्मा के क्षेत्र में दिखाई देता है, और यह तुरंत दिखाता है कि कट दूरी के अनुसार अभिसरण का अर्थ बाएं-अभिसरण है। | ||
व्युत्क्रम काउंटिंग लेम्मा। प्रत्येक वास्तविक संख्या के लिए <math>\epsilon > 0</math>, एक वास्तविक संख्या | व्युत्क्रम काउंटिंग लेम्मा। प्रत्येक वास्तविक संख्या के लिए <math>\epsilon > 0</math>, एक वास्तविक संख्या सम्मलित है <math>\eta > 0</math> और एक सकारात्मक पूर्णांक <math>k</math> ऐसा कि किसी भी जोड़ी ग्राफोन के लिए <math>U</math> और <math>W</math> साथ | ||
<math display=block> |t(F, U) - t(F, W)| \le \eta </math> | <math display=block> |t(F, U) - t(F, W)| \le \eta </math> | ||
सभी रेखांकन के लिए <math>F</math> संतुष्टि देने वाला <math>v(F) \le k</math>, | सभी रेखांकन के लिए <math>F</math> संतुष्टि देने वाला <math>v(F) \le k</math>, | ||
| Line 248: | Line 248: | ||
यह स्थान सघन स्थान बन जाता है। | यह स्थान सघन स्थान बन जाता है। | ||
इसके | इसके अतिरिक्त, इसमें सभी परिमित रेखांकन का सेट होता है, जो उनके संबंधित ग्राफों द्वारा एक सघन सेट के रूप में दर्शाया जाता है। | ||
इन अवलोकनों से पता चलता है कि ग्राफ़ॉन का स्थान एक पूर्ण_मीट्रिक_स्थान है#कट की गई दूरी के संबंध में ग्राफ़ के स्थान का पूरा होना। इसका एक तात्कालिक परिणाम निम्नलिखित है। | इन अवलोकनों से पता चलता है कि ग्राफ़ॉन का स्थान एक पूर्ण_मीट्रिक_स्थान है#कट की गई दूरी के संबंध में ग्राफ़ के स्थान का पूरा होना। इसका एक तात्कालिक परिणाम निम्नलिखित है। | ||
| Line 275: | Line 275: | ||
</ब्लॉककोट> | </ब्लॉककोट> | ||
लेकिन इसका उपयोग मजबूत नियमितता परिणाम | लेकिन इसका उपयोग मजबूत नियमितता परिणाम सिद्ध करने के लिए किया जा सकता है, जैसे कि ज़ेमेरीडी नियमितता लेम्मा#मजबूत नियमितता लेम्मा : | ||
ग्राफों के लिए मजबूत नियमितता लेम्मा। हर क्रम के लिए <math>\mathbf{\epsilon} = (\epsilon_0, \epsilon_1, \dots)</math> धनात्मक वास्तविक संख्याओं का, एक धनात्मक पूर्णांक होता है <math>S</math> ऐसा है कि हर ग्राफॉन के लिए <math>W</math>, एक ग्राफन है <math>W'</math> और एक स्टेपफंक्शन <math>U</math> साथ <math>k < S</math> ऐसे कदम <math> \lVert W - W' \rVert_1 \le \epsilon_0 </math> और <math> \lVert W' - U \rVert_\square \le \epsilon_k.</math> | ग्राफों के लिए मजबूत नियमितता लेम्मा। हर क्रम के लिए <math>\mathbf{\epsilon} = (\epsilon_0, \epsilon_1, \dots)</math> धनात्मक वास्तविक संख्याओं का, एक धनात्मक पूर्णांक होता है <math>S</math> ऐसा है कि हर ग्राफॉन के लिए <math>W</math>, एक ग्राफन है <math>W'</math> और एक स्टेपफंक्शन <math>U</math> साथ <math>k < S</math> ऐसे कदम <math> \lVert W - W' \rVert_1 \le \epsilon_0 </math> और <math> \lVert W' - U \rVert_\square \le \epsilon_k.</math> | ||
| Line 305: | Line 305: | ||
ग्राफोन स्वाभाविक रूप से सघन सरल रेखांकन से जुड़े होते हैं। | ग्राफोन स्वाभाविक रूप से सघन सरल रेखांकन से जुड़े होते हैं। | ||
सघन निर्देशित भारित रेखांकन के लिए इस मॉडल के विस्तार हैं, जिन्हें | सघन निर्देशित भारित रेखांकन के लिए इस मॉडल के विस्तार हैं, जिन्हें अधिकांशत: अलंकृत ग्राफॉन कहा जाता है।{{r|decorate}} रेंडम ग्राफ मॉडल के दोनों दृष्टिकोणों से विरल ग्राफ शासन के हाल के विस्तार भी हैं <ref name=Veitch:Roy:2015 />और ग्राफ सीमा सिद्धांत भी है।<ref name=Borgs:Chayes:Cohn:Zhao:2014:sgc1 /><ref name=Borgs:Chayes:Cohn:Zhao:2014:sgc2 /> | ||
Revision as of 15:29, 18 May 2023
File:Exchangeable random graph from graphon.png
एक ग्राफॉन द्वारा परिभाषित विनिमेय यादृच्छिक ग्राफ का अहसास। ग्राफॉन को मैजेंटा हीटमैप (निचले दाएं) के रूप में दिखाया गया है। आकार का एक यादृच्छिक ग्राफ स्वतंत्र रूप से प्रत्येक शीर्ष को असाइन करके उत्पन्न होता है एक अव्यक्त यादृच्छिक चर (ऊर्ध्वाधर अक्ष के साथ मान) और प्रत्येक शीर्ष सहित संभावना के साथ स्वतंत्र रूप से . उदाहरण के लिए, किनारा (हरा, बिंदीदार) संभावना के साथ सम्मलित है ; दाहिने वर्ग में हरे बक्से का प्रतिनिधित्व करते हैं के मूल्य और . ऊपरी बाएँ पैनल ग्राफ प्राप्ति को आसन्न आव्यूह के रूप में दिखाता है।
ग्राफ़ सिद्धांत और सांख्यिकी में, एक ग्राफ़ॉन (जिसे ग्राफ़ सीमा के रूप में भी जाना जाता है) एक सममित फलन औसत दर्जे का कार्य है: