ग्राफॉन: Difference between revisions

Revision as of 17:48, 17 May 2023

एक ग्राफॉन द्वारा परिभाषित विनिमेय यादृच्छिक ग्राफ का अहसास। ग्राफॉन को मैजेंटा हीटमैप (निचले दाएं) के रूप में दिखाया गया है। आकार का एक यादृच्छिक ग्राफ

n

स्वतंत्र रूप से प्रत्येक शीर्ष को असाइन करके उत्पन्न होता है

k\in \{1,\dotsc ,n\}

एक अव्यक्त यादृच्छिक चर

U_{k}\sim \mathrm {U} (0,1)

(ऊर्ध्वाधर अक्ष के साथ मान) और प्रत्येक किनारे सहित

(k,l)

संभावना के साथ स्वतंत्र रूप से

f(U_{k},U_{l})

. उदाहरण के लिए, किनारा

(3,5)

(हरा, बिंदीदार) संभावना के साथ मौजूद है

f(0.72,0.9)

; दाहिने वर्ग में हरे बक्से का प्रतिनिधित्व करते हैं के मूल्य

(u_{3},u_{5})

और

(u_{5},u_{3})

. ऊपरी बाएँ पैनल ग्राफ प्राप्ति को आसन्न आव्यूह के रूप में दिखाता है।

ग्राफ़ सिद्धांत और सांख्यिकी में, एक ग्राफ़ॉन (जिसे ग्राफ़ सीमा के रूप में भी जाना जाता है) एक सममित फलन औसत दर्जे का कार्य है: $W:[0,1]^{2}\to [0,1]$ , जो सघन रेखांकन के अध्ययन में महत्वपूर्ण है। सघन रेखांकन के अनुक्रम की सीमा के लिए ग्राफ़न्स एक प्राकृतिक धारणा के रूप में उत्पन्न होते हैं, और विनिमेय यादृच्छिक चर यादृच्छिक ग्राफ़ मॉडल की मौलिक परिभाषित वस्तुओं के रूप में हैं। ग्राफ़ॉन निम्नलिखित प्रेक्षणों के युग्म द्वारा सघन ग्राफ़ से बंधे हैं: ग्राफ़ॉन द्वारा परिभाषित यादृच्छिक ग्राफ़ मॉडल लगभग निश्चित रूप से सघन ग्राफ़ को वृद्धि देते हैं, और, नियमितता लेम्मा द्वारा, ग्राफ़ॉन यादृच्छिक बड़े सघन ग्राफ़ की संरचना को प्रग्रहण करते हैं।

सांख्यिकीय सूत्रीकरण

एक ग्राफॉन एक सममित मापने योग्य कार्य है $W:[0,1]^{2}\to [0,1]$ . आमतौर पर एक ग्राफॉन को निम्न योजना के अनुसार विनिमेय यादृच्छिक ग्राफ मॉडल को परिभाषित करने के रूप में समझा जाता है:

प्रत्येक शीर्ष $j$ ग्राफ का एक स्वतंत्र यादृच्छिक मान नियुक्त किया गया है $u_{j}\sim U[0,1]$ ।
किनारा $(i,j)$ संभावना के साथ ग्राफ में स्वतंत्र रूप से शामिल है $W(u_{i},u_{j})$ ।

एक यादृच्छिक ग्राफ मॉडल एक विनिमेय यादृच्छिक ग्राफ मॉडल है और केवल इसे इस तरह (संभवतः यादृच्छिक) ग्राफॉन के संदर्भ में परिभाषित किया जा सकता है। एक निश्चित ग्राफॉन पर अर्द्धरित मॉडल $W$ कभी-कभी निरूपित किया जाता है $\mathbb {G} (n,W)$ , यादृच्छिक रेखांकन के एर्डोस-रेनी मॉडल के अनुरूप। ग्राफॉन से उत्पन्न ग्राफ $W$ इस प्रकार कहा जाता है $W$ -यादृच्छिक ग्राफ है।

यह इस परिभाषा और बड़ी संख्या के कानून से चलता है कि, यदि $W\neq 0$ विनिमेय यादृच्छिक ग्राफ मॉडल लगभग निश्चित रूप से सघन हैं।^[1]

उदाहरण

ग्राफॉन का सबसे सरल उदाहरण है $W(x,y)\equiv p$ कुछ स्थिर के लिए $p\in [0,1]$ . इस मामले में संबंधित विनिमेय यादृच्छिक ग्राफ मॉडल एर्डोस-रेनी मॉडल है $G(n,p)$ जिसमें संभाव्यता के साथ स्वतंत्र रूप से प्रत्येक किनारा शामिल है $p$ ।

यदि हम इसके बजाय एक ग्राफ़ॉन के साथ शुरू करते हैं जो टुकड़े वार स्थिर है:

इकाई वर्ग को विभाजित करना $k\times k$ ब्लॉक, और
सेटिंग $W$ क�

[1]

@@ Line 85: / Line 85: @@
 ==== अर्द्ध ग्राफॉन ====
-क्रम लीजिए <math>(H_n)</math> [[आधा ग्राफ|अर्द्ध ग्राफ]] का अर्द्ध ग्राफ, लेने से परिभाषित <math>H_n</math> द्विदलीय ग्राफ पर होना <math>2n</math> वर्टेक्स <math>u_1, u_2, \dots, u_n</math> और <math>v_1, v_2, \dots, v_{n}</math> ऐसा है कि <math>u_i</math> लगी हुई है <math>v_j</math> ठीक है जब <math>i\le j</math>. यदि शीर्षों को प्रस्तुत क्रम में सूचीबद्ध किया गया है, तब
+<math>(H_n)</math> [[आधा ग्राफ|अर्द्ध ग्राफ]] का क्रम लीजिए अर्द्ध ग्राफ, लेने से परिभाषित <math>H_n</math> द्विदलीय ग्राफ पर होना <math>2n</math> वर्टेक्स <math>u_1, u_2, \dots, u_n</math> और <math>v_1, v_2, \dots, v_{n}</math> ऐसा है कि <math>u_i</math> लगी हुई है <math>v_j</math> ठीक है जब <math>i\le j</math> है. यदि शीर्षों को प्रस्तुत क्रम में सूचीबद्ध किया गया है, तब
-निकटता आव्यूह <math>A_{H_n}</math> अर्द्ध वर्ग ब्लॉक आव्यूह के दो वर्टेक्स भरे हुए हैं, शेष प्रविष्टियाँ शून्य के बराबर हैं।
+निकटतम आव्यूह <math>A_{H_n}</math>अर्द्ध वर्ग ब्लॉक आव्यूह के दो वर्टेक्स पूरित हैं, शेष प्रविष्टियाँ शून्य के बराबर हैं।
 उदाहरण के लिए, आसन्न आव्यूह <math>H_{3}</math> द्वारा दिया गया है
 <math display=block> \begin{bmatrix} 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0\end{bmatrix}.</math>
-जैसा <math>n</math> बड़े हो जाते हैं, उनके ये वर्टेक्स चिकने हो जाते हैं।
+जैसा <math>n</math> बड़े हो जाते हैं, उनके ये वर्टेक्स निर्बाध हो जाते हैं।
-इस अंतर्ज्ञान का मिलान, अनुक्रम <math>(H_n)</math> अर्द्ध ग्राफॉन में परिवर्तित हो जाता है <math>W</math> द्वारा परिभाषित <math>W(x,y) = 1</math> कब <math>|x-y| \ge 1/2</math> और <math>W(x,y) = 0</math> अन्यथा।
+इस अंतर्ज्ञान का मिलान, अनुक्रम <math>(H_n)</math> अर्द्ध ग्राफॉन में परिवर्तित हो जाता है <math>W</math> द्वारा परिभाषित <math>W(x,y) = 1</math> जब <math>|x-y| \ge 1/2</math> और <math>W(x,y) = 0</math>।
 ==== पूर्ण द्विदलीय ग्राफॉन ====
-क्रम लीजिए <math>(K_{n,n})</math> समान आकार के भागों के साथ पूर्ण द्विदलीय ग्राफ का।
+क्रम लीजिए <math>(K_{n,n})</math> समान आकार के भागों के साथ पूर्ण द्विदलीय ग्राफ का क्रम लीजिए।
 यदि हम शुरुआत में सभी शीर्षों को एक भाग में रखकर शीर्षों को क्रमित करते हैं
 और दूसरे भाग के शीर्षों को अंत में रखकर,
-की निकटता आव्यूह <math>(K_{n,n})</math> एक ब्लॉक ऑफ-विकर्ण आव्यूह की तरह दिखता है, जिसमें दो ब्लॉक और शून्य के दो ब्लॉक होते हैं।
+निकटतम आव्यूह <math>(K_{n,n})</math> एक ब्लॉक ऑफ-विकर्ण आव्यूह की तरह दिखता है, जिसमें दो ब्लॉक और शून्य के दो ब्लॉक होते हैं।
 उदाहरण के लिए, आसन्न आव्यूह <math>K_{2,2}</math> द्वारा दिया गया है
@@ Line 103: / Line 103: @@
 जैसा <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> भागों के बीच बारी-बारी से,
@@ Line 110: / Line 110: @@
 <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>(K_{n,n})</math> अद्वितीय होने के लिए और उदाहरण 3 से ग्राफॉन में परिणाम।
+इस व्यवहार के बावजूद, हम अभी भी चाहते हैं की सीमा <math>(K_{n,n})</math> अद्वितीय हो और परिणाम उदाहरण 3 से ग्राफॉन में हो।
 इसका मतलब यह है कि जब हम औपचारिक रूप से रेखांकन के अनुक्रम के लिए अभिसरण को परिभाषित करते हैं, तो एक सीमा की परिभाषा शीर्षों के पुन: लेबलिंग के लिए अज्ञेयवादी होनी चाहिए।
 ==== ए-यादृच्छिक रेखांकन की सीमा ====
-एक यादृच्छिक क्रम लें <math>(G_n)</math> ग्राफॉन का#सांख्यिकीय_सूत्रीकरण | <math>W</math>ड्राइंग द्वारा यादृच्छिक रेखांकन <math>G_n \sim \mathbb{G}(n, W)</math> कुछ निश्चित ग्राफॉन के लिए <math>W</math>.
+एक यादृच्छिक क्रम <math>(G_n)</math> ग्राफॉन का#सांख्यिकीय_सूत्रीकरण लें। <math>W</math> आहरण आरेख द्वारा यादृच्छिक रेखांकन <math>G_n \sim \mathbb{G}(n, W)</math> कुछ निश्चित ग्राफॉन के लिए <math>W</math>.
 फिर इस खंड से पहले उदाहरण की तरह, यह पता चला है <math>(G_n)</math> में विलीन हो जाता है <math>W</math> लगभग निश्चित रूप से।
 === ग्राफोन से ग्राफ पैरामीटर पुनर्प्राप्त करना ===
-दिया गया ग्राफ <math>G</math> संबद्ध ग्राफॉन के साथ <math>W = W_G</math>, हम ग्राफ सैद्धांतिक गुणों और मापदंडों को पुनर्प्राप्त कर सकते हैं <math>G</math> के परिवर्तनों को एकीकृत करके <math>W</math>. उदाहरण के लिए, किनारे का घनत्व (अर्थात शीर्षों की संख्या से विभाजित औसत डिग्री)। <math>G</math> अभिन्न द्वारा दिया गया है
+दिया गया ग्राफ <math>G</math> संबद्ध ग्राफॉन के साथ <math>W = W_G</math>, हम ग्राफ  <math>G</math> सैद्धांतिक गुणों और मापदंडों को पुनर्प्राप्त कर सकते हैं <math>W</math> के परिवर्तनों को एकीकृत करके। उदाहरण के लिए, किनारे का घनत्व (अर्थात शीर्षों की संख्या से विभाजित औसत डिग्री)। <math>G</math> अभिन्न द्वारा दिया गया है:
 <math display=block> \int_{0}^1 \int_0^1 W(x,y) \; \mathrm{d}x \, \mathrm{d}y .</math>
 यह है क्योंकि <math>W</math> है <math>\{0,1\}</math>-मूल्यवान, और प्रत्येक किनारा <math>(i, j)</math>
 में <math>G</math> एक क्षेत्र से मेल खाता है <math>I_i \times I_j</math>
-क्षेत्र के <math>1/n^2</math> कहाँ <math>W</math> के बराबर होती है <math>1</math>.
+क्षेत्र के <math>1/n^2</math> जहाँ <math>W</math> के बराबर होती है <math>1</math>.
 इसी तरह के तर्क से पता चलता है कि त्रिभुजों की संख्या में <math>G</math> के बराबर है

Anonymous

Search

ग्राफॉन: Difference between revisions

Namespaces

More

Page actions

Revision as of 17:48, 17 May 2023

Contents

सांख्यिकीय सूत्रीकरण

उदाहरण