यादृच्छिक ग्राफ: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(5 intermediate revisions by 3 users not shown)
Line 8: Line 8:
यादृच्छिक ग्राफ n अलग-अलग कोने के समूह से प्रारम्भ करके और यादृच्छिक रूप से उनके बीच क्रमिक किनारों को जोड़कर प्राप्त किया जाता है। इस क्षेत्र में अध्ययन का उद्देश्य यह निर्धारित करना है कि ग्राफ की एक विशेष गुण किस स्तर पर उत्पन्न होने की संभावना है।<ref name = "Random Graphs2">[[Béla Bollobás]], ''Random Graphs'', 1985, Academic Press Inc., London Ltd.</ref> अलग-अलग यादृच्छिक ग्राफ़ मॉडल ग्राफ़ पर अलग-अलग संभाव्यता वितरण उत्पन्न करते हैं। [[एडगर गिल्बर्ट]] द्वारा प्रस्तावित सबसे सामान्यतः अध्ययन किया जाने वाला है। जिसे ''G''(''n'',''p'') निरूपित किया गया है। जिसमें प्रत्येक संभावित बढ़त स्वतंत्र रूप से प्रायिकता 0 < ''p'' < 1 के साथ होती है। m किनारों के साथ<math>N = \tbinom{n}{2}</math> ''किसी एक विशेष'' यादृच्छिक ग्राफ को प्राप्त करने की प्रायिकता <math>p^m (1-p)^{N-m}</math> है।<ref name = "Random Graphs3">[[Béla Bollobás]], ''Probabilistic Combinatorics and Its Applications'', 1991, Providence, RI: American Mathematical Society.</ref>
यादृच्छिक ग्राफ n अलग-अलग कोने के समूह से प्रारम्भ करके और यादृच्छिक रूप से उनके बीच क्रमिक किनारों को जोड़कर प्राप्त किया जाता है। इस क्षेत्र में अध्ययन का उद्देश्य यह निर्धारित करना है कि ग्राफ की एक विशेष गुण किस स्तर पर उत्पन्न होने की संभावना है।<ref name = "Random Graphs2">[[Béla Bollobás]], ''Random Graphs'', 1985, Academic Press Inc., London Ltd.</ref> अलग-अलग यादृच्छिक ग्राफ़ मॉडल ग्राफ़ पर अलग-अलग संभाव्यता वितरण उत्पन्न करते हैं। [[एडगर गिल्बर्ट]] द्वारा प्रस्तावित सबसे सामान्यतः अध्ययन किया जाने वाला है। जिसे ''G''(''n'',''p'') निरूपित किया गया है। जिसमें प्रत्येक संभावित बढ़त स्वतंत्र रूप से प्रायिकता 0 < ''p'' < 1 के साथ होती है। m किनारों के साथ<math>N = \tbinom{n}{2}</math> ''किसी एक विशेष'' यादृच्छिक ग्राफ को प्राप्त करने की प्रायिकता <math>p^m (1-p)^{N-m}</math> है।<ref name = "Random Graphs3">[[Béla Bollobás]], ''Probabilistic Combinatorics and Its Applications'', 1991, Providence, RI: American Mathematical Society.</ref>


एक निकटतम संबंधित मॉडल एर्डोस-रेनी मॉडल ''G''(''n'',''M'') को दर्शाता है। बिल्कुल ''M'' किनारों वाले सभी ग्राफों के लिए समान संभावना प्रदान करता है। 0 ≤ ''M'' ≤ ''N'' के साथ ''G''(''n'',''M'') है। <math>\tbinom{N}{M}</math> तत्व और प्रत्येक तत्व प्रायिकता के साथ होता <math>1/\tbinom{N}{M}</math> है।<ref name="Random Graphs2" /> बाद वाले मॉडल को 'यादृच्छिक ग्राफ प्रक्रिया' के एक विशेष समय (''M'') पर एक स्नैपशॉट के रूप में देखा जा सकता है। <math>\tilde{G}_n</math>, जो एक [[अनेक संभावनाओं में से चुनी हूई प्रक्रिया]] है। जो n कोने और बिना किनारों से प्रारम्भ होती है और प्रत्येक चरण में किनारों के समूह से समान रूप से चुने गए नए किनारे को जोड़ती है।
एक निकटतम संबंधित मॉडल एर्डोस-रेनी मॉडल ''G''(''n'',''M'') को दर्शाता है। बिल्कुल ''M'' किनारों वाले सभी ग्राफों के लिए समान संभावना प्रदान करता है। 0 ≤ ''M'' ≤ ''N'' के साथ ''G''(''n'',''M'') है। <math>\tbinom{N}{M}</math> तत्व और प्रत्येक तत्व प्रायिकता के साथ होता <math>1/\tbinom{N}{M}</math> है।<ref name="Random Graphs2" /> बाद वाले मॉडल को 'यादृच्छिक ग्राफ प्रक्रिया' के एक विशेष समय (''M'') पर एक स्नैपशॉट के रूप में देखा जा सकता है। <math>\tilde{G}_n</math>, जो एक [[अनेक संभावनाओं में से चुनी हूई प्रक्रिया]] है। जो n कोने और बिना किनारों से प्रारम्भ होती है और प्रत्येक चरण में किनारों के समूह से समान रूप से चुने गए नए किनारे को जोड़ती है।


यदि इसके अतिरिक्त हम वर्टिकल के अनंत समूह के साथ प्रारम्भ करते हैं और फिर से प्रत्येक संभावित किनारे को प्रायिकता 0 <p <1 के साथ स्वतंत्र रूप से होने देते हैं। तो हमें एक वस्तु G मिलती है। जिसे 'अनंत यादृच्छिक ग्राफ' कहा जाता है। कुछ स्थितियों को छोड़कर जहां p, 0 या 1 के बीच में है। ऐसे G में [[लगभग निश्चित रूप से]] निम्नलिखित गुण होती है:
यदि इसके अतिरिक्त हम वर्टिकल के अनंत समूह के साथ प्रारम्भ करते हैं और फिर से प्रत्येक संभावित किनारे को प्रायिकता 0 <p <1 के साथ स्वतंत्र रूप से होने देते हैं। तो हमें एक वस्तु G मिलती है। जिसे 'अनंत यादृच्छिक ग्राफ' कहा जाता है। कुछ स्थितियों को छोड़कर जहां p, 0 या 1 के बीच में है। ऐसे G में [[लगभग निश्चित रूप से]] निम्नलिखित गुण होती है:
Line 18: Line 18:
एक अन्य मॉडल, जो गिल्बर्ट के यादृच्छिक ग्राफ मॉडल का सामान्यीकरण करता है, यादृच्छिक डॉट-उत्पाद मॉडल है। यादृच्छिक डॉट-उत्पाद ग्राफ प्रत्येक शीर्ष के साथ एक [[वास्तविक वेक्टर|रियल वेक्टर]] को जोड़ता है। किसी भी कोने ''u'' और ''v'' के बीच किनारे ''uv'' की संभावना उनके संबंधित वैक्टर के [[डॉट उत्पाद|डॉट प्रोडक्ट]] u • v का कार्य है।
एक अन्य मॉडल, जो गिल्बर्ट के यादृच्छिक ग्राफ मॉडल का सामान्यीकरण करता है, यादृच्छिक डॉट-उत्पाद मॉडल है। यादृच्छिक डॉट-उत्पाद ग्राफ प्रत्येक शीर्ष के साथ एक [[वास्तविक वेक्टर|रियल वेक्टर]] को जोड़ता है। किसी भी कोने ''u'' और ''v'' के बीच किनारे ''uv'' की संभावना उनके संबंधित वैक्टर के [[डॉट उत्पाद|डॉट प्रोडक्ट]] u • v का कार्य है।


[[नेटवर्क संभाव्यता मैट्रिक्स]] किनारे की संभावनाओं के माध्यम से यादृच्छिक रेखांकन करता है। जो <math>p_{i,j}</math> संभावना का प्रतिनिधित्व करता है। वह दिया हुआ किनारा <math>e_{i,j}</math> एक निर्दिष्ट समय अवधि के लिए उपस्थित है। यह मॉडल निर्देशित और अप्रत्यक्ष रूप से एक्स्टेंसिबल है; भारित और भारित और स्थिर या गतिशील रेखांकन संरचना भी उस्थित होता है।
[[नेटवर्क संभाव्यता मैट्रिक्स]] किनारे की संभावनाओं के माध्यम से यादृच्छिक रेखांकन करता है। जो <math>p_{i,j}</math> संभावना का प्रतिनिधित्व करता है। वह दिया हुआ किनारा <math>e_{i,j}</math> एक निर्दिष्ट समय अवधि के लिए उपस्थित है। यह मॉडल निर्देशित और अप्रत्यक्ष रूप से एक्स्टेंसिबल है; भारित और भारित और स्थिर या गतिशील रेखांकन संरचना भी उस्थित होता है।


''M'' ≃ ''pN'' के लिए, जहां ''N'' संभव किनारों की अधिकतम संख्या है, दो सबसे व्यापक रूप से प्रयोग किए जाने वाले मॉडल, ''G''(''n'',''M'') और ''G''(''n'',''p'') लगभग विनिमेय हैं।<ref name="Handbook">[[Béla Bollobás|Bollobas, B.]] and Riordan, O.M. "Mathematical results on scale-free random graphs" in "Handbook of Graphs and Networks" (S. Bornholdt and H.G. Schuster (eds)), Wiley VCH, Weinheim, 1st ed., 2003</ref>
''M'' ≃ ''pN'' के लिए, जहां ''N'' संभव किनारों की अधिकतम संख्या है, दो सबसे व्यापक रूप से प्रयोग किए जाने वाले मॉडल, ''G''(''n'',''M'') और ''G''(''n'',''p'') लगभग विनिमेय हैं।<ref name="Handbook">[[Béla Bollobás|Bollobas, B.]] and Riordan, O.M. "Mathematical results on scale-free random graphs" in "Handbook of Graphs and Networks" (S. Bornholdt and H.G. Schuster (eds)), Wiley VCH, Weinheim, 1st ed., 2003</ref>
Line 33: Line 33:


== गुण ==
== गुण ==
यादृच्छिक रेखांकन का सिद्धांत यादृच्छिक रेखांकन के विशिष्ट गुणों का अध्ययन करता है, जो किसी विशेष वितरण से तैयार किए गए रेखांकन के लिए उच्च संभावना रखते हैं। उदाप्रत्येकण के लिए, हम दिए गए मान के लिए पूछ सकते हैं <math>n</math> और <math>p</math> इसकी क्या संभावना है <math>G(n,p)</math> [[कनेक्शन (गणित)]] है। ऐसे प्रश्नों का अध्ययन करने में, शोधकर्ता अक्सर यादृच्छिक रेखांकन के स्पर्शोन्मुख व्यवहार पर ध्यान केंद्रित करते हैं - वे मूल्य जो विभिन्न संभावनाओं के रूप में परिवर्तित होते हैं <math>n</math> बहुत बड़ा हो जाता है। [[परकोलेशन सिद्धांत]] यादृच्छिक रेखांकन की संबद्धता की विशेषता बताता है, विशेष रूप से असीम रूप से बड़े वाले।
यादृच्छिक रेखांकन का सिद्धांत यादृच्छिक रेखांकन के विशिष्ट गुणों का अध्ययन करता है। जो किसी विशेष वितरण से तैयार किए गए रेखांकन के लिए उच्च संभावना रखते हैं। उदाहरण के लिए हम दिए गए मान <math>n</math> और <math>p</math> के लिए पूछ सकते हैं। इसकी क्या संभावना है। <math>G(n,p)</math> [[कनेक्शन (गणित)]] है। ऐसे प्रश्नों का अध्ययन करने में शोधकर्ता अधिकांशतः यादृच्छिक रेखांकन के स्पर्शोन्मुख व्यवहार पर ध्यान केंद्रित करते हैं। वे मूल्य, जो विभिन्न संभावनाओं के रूप में परिवर्तित होते हैं, <math>n</math> बहुत बड़ा हो जाता है। [[परकोलेशन सिद्धांत]] यादृच्छिक रेखांकन की संबद्धता की विशेषता बताता है।


परकोलेशन ग्राफ की मजबूती से संबंधित है (जिसे नेटवर्क भी कहा जाता है)। का एक यादृच्छिक ग्राफ दिया <math>n</math> नोड्स और एक औसत डिग्री <math>\langle k\rangle</math>. अगला हम बेतरतीब ढंग से एक अंश निकालते हैं <math>1-p</math> नोड्स की और केवल एक अंश छोड़ दें <math>p</math>. एक महत्वपूर्ण रिसाव सीमा उपस्थित है <math>p_c=\tfrac{1}{\langle k\rangle}</math> जिसके नीचे ऊपर रहते हुए नेटवर्क खंडित हो जाता है <math>p_c</math> एक विशाल जुड़ा हुआ घटक उपस्थित है।<ref name="Random Graphs" /><ref name="Handbook" /><ref name="Random graphs" /><ref>{{cite book  |title=Networks: An Introduction |last= Newman |first=M. E. J. |year= 2010 |publisher=  Oxford}}</ref><ref name="On Random Graphs" />
परकोलेशन ग्राफ की दृढ़ता से संबंधित है (जिसे नेटवर्क भी कहा जाता है)। <math>n</math> नोड्स का एक यादृच्छिक ग्राफ दिया और औसत डिग्री <math>\langle k\rangle</math> है। अगला हम भिन्न के <math>1-p</math> नोड्स को हटाते हैं और केवल एक भिन्न <math>p</math> छोड़ देत हैं। <math>p_c=\tfrac{1}{\langle k\rangle}</math> एक महत्वपूर्ण रिसाव सीमा उपस्थित है। जिसके नीचे ऊपर रहते हुए नेटवर्क <math>p_c</math> टूट जाता है और एक बड़ा जुड़ा हुआ घटक उपस्थित है।<ref name="Random Graphs" /><ref name="Handbook" /><ref name="Random graphs" /><ref>{{cite book  |title=Networks: An Introduction |last= Newman |first=M. E. J. |year= 2010 |publisher=  Oxford}}</ref><ref name="On Random Graphs" />


स्थानीयकृत परकोलेशन एक नोड को उसके पड़ोसियों, अगले निकटतम पड़ोसियों आदि को एक अंश तक हटाने के लिए संदर्भित करता है <math>1-p</math> नेटवर्क से नोड्स हटा दिए जाते हैं। यह दिखाया गया था कि डिग्री के प्वासों वितरण के साथ यादृच्छिक ग्राफ के लिए <math>p_c=\tfrac{1}{\langle k\rangle}</math> बिल्कुल यादृच्छिक हटाने के लिए।
स्थानीयकृत परकोलेशन एक नोड को उसके निकटम अगले निकटतम आदि को एक भिन्न तक हटाने के लिए संदर्भित करता है। जब तक <math>1-p</math> नेटवर्क से नोड्स हटा दिए जाते हैं। यह दिखाया गया था कि डिग्री <math>p_c=\tfrac{1}{\langle k\rangle}</math> के पॉसों वितरण के साथ यादृच्छिक ग्राफ के लिए बिल्कुल यादृच्छिक हटाने के लिए भी उपस्थित है।


संभाव्यता पद्धति में रैंडम ग्राफ़ का व्यापक रूप से उपयोग किया जाता है, जहाँ कोई कुछ गुणों वाले ग्राफ़ के अस्तित्व को सिद्ध करने का प्रयास करता है। एक यादृच्छिक ग्राफ पर एक गुण का अस्तित्व अक्सर ज़ेमेरीडी नियमितता लेम्मा के माध्यम से, लगभग सभी ग्राफों पर उस गुण के अस्तित्व का संकेत दे सकता है।
संभाव्यता पद्धति में रैंडम ग्राफ़ का व्यापक रूप से उपयोग किया जाता है। जहाँ कोई कुछ गुणों वाले ग्राफ़ के अस्तित्व को सिद्ध करने का प्रयास करता है। यादृच्छिक ग्राफ पर एक गुण का अस्तित्व अधिकांशतः ज़ेमेरीडी नियमितता लेम्मा के माध्यम से लगभग सभी ग्राफों पर उस गुण के अस्तित्व का संकेत दे सकता है।


यादृच्छिक नियमित रेखांकन में, <math>G(n,r-reg)</math> का समूह हैं <math>r</math>-नियमित रेखांकन के साथ <math>r = r(n)</math> ऐसा है कि <math>n</math> और <math>m</math> प्राकृतिक संख्या हैं, <math>3 \le r  < n</math>, और <math>rn = 2m</math> सम है।<ref name="Random Graphs2" />
यादृच्छिक नियमित रेखांकन में <math>G(n,r-reg)</math> का समूह हैं, <math>r</math>-नियमित रेखांकन के साथ <math>r = r(n)</math> ऐसा है कि <math>n</math> और <math>m</math> प्राकृतिक संख्या हैं और <math>3 \le r  < n</math>, और <math>rn = 2m</math> सम है।<ref name="Random Graphs2" />


एक ग्राफ का डिग्री अनुक्रम <math>G</math> में <math>G^n</math> समूह में केवल किनारों की संख्या पर निर्भर करता है<ref name="Random Graphs2" />:<math>V_n^{(2)} = \left \{ij \ : \ 1 \leq j \leq n, i \neq j \right \} \subset V^{(2)}, \qquad  i=1, \cdots, n.</math>
एक ग्राफ का डिग्री अनुक्रम <math>G</math> में <math>G^n</math> समूह में केवल किनारों की संख्या <math>V_n^{(2)} = \left \{ij \ : \ 1 \leq j \leq n, i \neq j \right \} \subset V^{(2)}, \qquad  i=1, \cdots, n.</math> पर निर्भर करता है<ref name="Random Graphs2" />
अगर किनारे, <math>M</math> एक यादृच्छिक ग्राफ में <math>G_M</math> यह सुनिश्चित करने के लिए काफी बड़ा है कि लगभग प्रत्येक <math>G_M</math> न्यूनतम डिग्री कम से कम 1 है, तो लगभग प्रत्येक <math>G_M</math> जुड़ा हुआ है और, अगर <math>n</math> सम है, लगभग प्रत्येक <math>G_M</math> पूर्ण मिलान है। विशेष रूप से, जिस क्षण लगभग प्रत्येक यादृच्छिक ग्राफ में अंतिम पृथक शीर्ष गायब हो जाता है, ग्राफ जुड़ा हो जाता है।<ref name="Random Graphs2" />


लगभग प्रत्येक ग्राफ़ प्रक्रिया सम संख्याओं पर होती है, जिसके किनारे न्यूनतम डिग्री को 1 तक बढ़ाते हैं या एक यादृच्छिक ग्राफ़ से थोड़ा अधिक होता है <math>\tfrac{n}{4}\log(n)</math> किनारों और 1 के करीब संभावना के साथ यह सुनिश्चित करता है कि ग्राफ़ में पूर्ण मिलान हो, अधिकतम एक शीर्ष के अपवाद के साथ।
यदि किनारे <math>M</math> एक यादृच्छिक ग्राफ में <math>G_M</math> यह सुनिश्चित करने के लिए अधिक बड़ा है कि लगभग प्रत्येक <math>G_M</math> न्यूनतम डिग्री कम से कम 1 है। तो लगभग प्रत्येक <math>G_M</math> जुड़ा हुआ है और यदि <math>n</math> सम है। तो लगभग प्रत्येक <math>G_M</math> पूर्ण मिलान है। विशेष रूप से, जिस क्षण लगभग प्रत्येक यादृच्छिक ग्राफ में अंतिम पृथक शीर्ष विलुप्त हो जाता है, ग्राफ जुड़ जाता है।<ref name="Random Graphs2" />


कुछ स्थिर के लिए <math>c</math>, लगभग प्रत्येक लेबल वाले ग्राफ़ के साथ <math>n</math> शिखर और कम से कम <math>cn\log(n)</math> किनारों [[हैमिल्टनियन चक्र]] है। प्रायिकता 1 की ओर अग्रसर होने के साथ, वह विशेष किनारा जो न्यूनतम डिग्री को 2 तक बढ़ाता है, ग्राफ को हैमिल्टनियन बनाता है।
लगभग प्रत्येक ग्राफ़ प्रक्रिया सम संख्याओं पर होती है। जिसके किनारे न्यूनतम डिग्री को 1 तक बढ़ाते हैं या एक यादृच्छिक ग्राफ़ से थोड़ा अधिक होता है <math>\tfrac{n}{4}\log(n)</math> किनारों और 1 के निकटम संभावना के साथ यह सुनिश्चित करता है कि ग्राफ़ में पूर्ण मिलान अधिकतम एक शीर्ष के अपवाद के साथ हो।
 
कुछ स्थिर के लिए <math>c</math>, लगभग प्रत्येक लेबल वाले ग्राफ़ के साथ <math>n</math> शिखर और कम से कम <math>cn\log(n)</math> किनारों [[हैमिल्टनियन चक्र]] है। प्रायिकता 1 की ओर अग्रसर होने के साथ वह विशेष किनारा, जो न्यूनतम डिग्री को 2 तक बढ़ाता है और ग्राफ को हैमिल्टनियन बनाता है।
 
यादृच्छिक ग्राफ के गुण ग्राफ परिवर्तनों के अऩुसार बदल सकते हैं या अपरिवर्तित रह सकते हैं। उदाप्रत्येकण के लिए, अलिर्ज़ा माशघी | मशघी ए. एट अल। ने प्रदर्शित किया कि एक परिवर्तन जो यादृच्छिक ग्राफ़ को उनके किनारे-दोप्रत्येके ग्राफ़ (या लाइन ग्राफ़) में परिवर्तित करता है, लगभग समान डिग्री वितरण के साथ ग्राफ़ का एक समूह बनाता है। किन्तु डिग्री सहसंबंध और अधिक उच्च क्लस्टरिंग गुणांक के साथ इसका प्रयोग किया जाता है।<ref>{{cite journal|first1=A.|last1=Ramezanpour|first2=V.|last2=Karimipour|first3=A.|last3=Mashaghi|title=असंबद्ध नेटवर्क से सहसंबद्ध नेटवर्क बनाना|journal=Phys. Rev. E|volume=67|issue=46107|pages=046107|year=2003|doi=10.1103/PhysRevE.67.046107|pmid=12786436|bibcode=2003PhRvE..67d6107R|arxiv=cond-mat/0212469|s2cid=33054818 }}</ref>


यादृच्छिक ग्राफ के गुण ग्राफ परिवर्तनों के तहत बदल सकते हैं या अपरिवर्तित रह सकते हैं। उदाप्रत्येकण के लिए, अलिर्ज़ा माशघी | मशघी ए. एट अल। ने प्रदर्शित किया कि एक परिवर्तन जो यादृच्छिक ग्राफ़ को उनके किनारे-दोप्रत्येके ग्राफ़ (या लाइन ग्राफ़) में परिवर्तित करता है, लगभग समान डिग्री वितरण के साथ ग्राफ़ का एक समूह बनाता है, लेकिन डिग्री सहसंबंध और ए के साथ महत्वपूर्ण रूप से उच्च क्लस्टरिंग गुणांक।<ref>{{cite journal|first1=A.|last1=Ramezanpour|first2=V.|last2=Karimipour|first3=A.|last3=Mashaghi|title=असंबद्ध नेटवर्क से सहसंबद्ध नेटवर्क बनाना|journal=Phys. Rev. E|volume=67|issue=46107|pages=046107|year=2003|doi=10.1103/PhysRevE.67.046107|pmid=12786436|bibcode=2003PhRvE..67d6107R|arxiv=cond-mat/0212469|s2cid=33054818 }}</ref>




== रंग ==
== रंग ==
शीर्ष V (G) = {1, ..., n} के साथ ऑर्डर n के एक यादृच्छिक ग्राफ G को देखते हुए, रंगों की संख्या पर लालची एल्गोरिथ्म द्वारा, रंगों को 1, 2, ... रंगों से रंगा जा सकता है। (शीर्ष 1 रंगीन 1 है, शीर्ष 2 रंगीन 1 है यदि यह शीर्ष 1 के निकट नहीं है, अन्यथा यह 2 रंगीन है, आदि)।<ref name="Random Graphs2" />कई क्यू रंगों को दिए गए यादृच्छिक ग्राफ़ के उचित रंगों की संख्या, जिसे इसके [[रंगीन बहुपद]] कहा जाता है, अब तक अज्ञात है। पैरामीटर n और किनारों की संख्या m या कनेक्शन प्रायिकता p के साथ यादृच्छिक ग्राफ़ के रंगीन बहुपद के शून्य के स्केलिंग को सांकेतिक पैटर्न मिलान के आधार पर एक एल्गोरिथ्म का उपयोग करके अनुभवजन्य रूप से अध्ययन किया गया है।<ref name="Chromatic Polynomials of Random Graphs">{{cite journal | last1 = Van Bussel | first1 = Frank | last2 = Ehrlich | first2 = Christoph | last3 = Fliegner | first3 = Denny | last4 = Stolzenberg | first4 = Sebastian | last5 = Timme | first5 = Marc | year = 2010 | title = यादृच्छिक रेखांकन के रंगीन बहुपद| journal = J. Phys. A: Math. Theor. | volume = 43 | issue = 17| page = 175002 | doi = 10.1088/1751-8113/43/17/175002 | arxiv = 1709.06209 | bibcode = 2010JPhA...43q5002V | s2cid = 15723612 }}</ref>
शीर्ष V (G) = {1, ..., n} के साथ ऑर्डर n के एक यादृच्छिक ग्राफ G को देखते हुए रंगों की संख्या पर एल्गोरिथ्म द्वारा रंगों को 1, 2, ... रंगों से रंगा जा सकता है। (शीर्ष 1 रंगीन 1 है, शीर्ष 2 रंगीन 1 है। यदि यह शीर्ष 1 के निकट नहीं है। अन्यथा यह 2 रंगीन है, आदि)।<ref name="Random Graphs2" /> कई ''q'' रंगों को दिए गए यादृच्छिक ग्राफ़ के उचित रंगों की संख्या, जिसे इसके [[रंगीन बहुपद]] कहा जाता है, अब तक अज्ञात है। पैरामीटर n और किनारों की संख्या m या कनेक्शन प्रायिकता p के साथ यादृच्छिक ग्राफ़ के रंगीन बहुपद के शून्य के स्केलिंग को सांकेतिक पैटर्न मिलान के आधार पर एक एल्गोरिथ्म का उपयोग करके अनुभवजन्य रूप से अध्ययन किया गया है।<ref name="Chromatic Polynomials of Random Graphs">{{cite journal | last1 = Van Bussel | first1 = Frank | last2 = Ehrlich | first2 = Christoph | last3 = Fliegner | first3 = Denny | last4 = Stolzenberg | first4 = Sebastian | last5 = Timme | first5 = Marc | year = 2010 | title = यादृच्छिक रेखांकन के रंगीन बहुपद| journal = J. Phys. A: Math. Theor. | volume = 43 | issue = 17| page = 175002 | doi = 10.1088/1751-8113/43/17/175002 | arxiv = 1709.06209 | bibcode = 2010JPhA...43q5002V | s2cid = 15723612 }}</ref>




== रैंडम पेड़ ==
== रैंडम पेड़ ==
{{main|Random tree}}
{{main|सामान्य पेड़़}}
एक रैंडम [[ट्रीप]] एक ट्री (ग्राफ थ्योरी) या आर्बोरेसेंस (ग्राफ थ्योरी) है जो एक स्टोचैस्टिक प्रक्रिया द्वारा बनता है। क्रम n और आकार M(n) के यादृच्छिक रेखांकन की एक बड़ी श्रृंखला में क्रम k के पेड़ घटकों की संख्या का वितरण विषम रूप से पॉइसन वितरण है। [[ यादृच्छिक पेड़ | यादृच्छिक पेड़]] के प्रकारों में [[ एक समान फैला हुआ पेड़ | एक समान फैला हुआ पेड़]] , [[यादृच्छिक न्यूनतम फैले पेड़]], [[ यादृच्छिक बाइनरी ट्री | यादृच्छिक बाइनरी ट्री]] , ट्रैप, तेजी से रैंडम ट्री, [[ ब्राउनियन पेड़ | ब्राउनियन पेड़]] और [[ यादृच्छिक वन | यादृच्छिक वन]] शामिल हैं।
एक रैंडम [[ट्रीप]] एक ट्री (ग्राफ थ्योरी) या आर्बोरेसेंस (ग्राफ थ्योरी) है। जो एक स्टोचैस्टिक प्रक्रिया द्वारा बनता है। क्रम n और आकार M(n) के यादृच्छिक रेखांकन की एक बड़ी श्रृंखला में क्रम k के ट्री घटकों की संख्या का वितरण विषम रूप से पॉइसन वितरण है। रैंडम ट्री के प्रकारों में यूनिफॉर्म स्पैनिंग ट्री, रैंडम मिनिमम स्पैनिंग ट्री, रैंडम बाइनरी ट्री, ट्रैप, तेजी से रैंडम ट्री, ब्राउनियन ट्री और रैंडम फॉरेस्ट सम्मिलित हैं।


== सशर्त यादृच्छिक रेखांकन ==
== नियमानुसार यादृच्छिक रेखांकन ==


संभाव्यता स्थान पर परिभाषित दिए गए यादृच्छिक ग्राफ मॉडल पर विचार करें <math>(\Omega, \mathcal{F}, P)</math> और जाने <math>\mathcal{P}(G) : \Omega \rightarrow R^{m}</math> एक वास्तविक मूल्यवान फलन बनें जो प्रत्येक ग्राफ़ को निर्दिष्ट करता है <math>\Omega</math> एम गुणों का एक वेक्टर।
संभाव्यता स्थान पर परिभाषित दिए गए यादृच्छिक ग्राफ मॉडल <math>(\Omega, \mathcal{F}, P)</math> पर विचार करें और <math>\mathcal{P}(G) : \Omega \rightarrow R^{m}</math> एक वास्तविक मूल्यवान फलन बनें। जो प्रत्येक ग्राफ़ <math>\Omega</math> में ''m'' गुणों के वेक्टर को निर्दिष्ट करता है। 
एक निश्चित के लिए <math>\mathbf{p} \in R^{m}</math>, सशर्त यादृच्छिक रेखांकन वे मॉडल हैं जिनमें संभाव्यता मापी जाती है <math>P</math> सभी ग्राफों को शून्य प्रायिकता प्रदान करता है जैसे कि '<math>\mathcal{P}(G) \neq \mathbf{p} </math>.


विशेष मामले सशर्त रूप से समान यादृच्छिक ग्राफ हैं, जहां <math>P</math> निर्दिष्ट गुणों वाले सभी ग्राफ़ों को समान संभावना प्रदान करता है। उन्हें एर्डोस-रेनी मॉडल जी (एन, एम) के सामान्यीकरण के रूप में देखा जा सकता है, जब कंडीशनिंग जानकारी जरूरी नहीं कि किनारों की संख्या एम हो, लेकिन जो भी अन्य मनमाने ढंग से ग्राफ गुण है <math>\mathcal{P}(G)</math>. इस मामले में बहुत कम विश्लेषणात्मक परिणाम उपलब्ध हैं और औसत गुणों के अनुभवजन्य वितरण प्राप्त करने के लिए सिमुलेशन की आवश्यकता है।
एक निश्चित <math>\mathbf{p} \in R^{m}</math> के लिए सशर्त यादृच्छिक रेखांकन वे मॉडल हैं। जिनमें संभाव्यता <math>P</math> मापी जाती है। सभी ग्राफों को शून्य प्रायिकता प्रदान करता है जैसे कि '<math>\mathcal{P}(G) \neq \mathbf{p} </math>.
 
विशेष स्थिति सशर्त रूप से समान यादृच्छिक ग्राफ हैं। जहां <math>P</math> निर्दिष्ट गुणों वाले सभी ग्राफ़ों को समान संभावना प्रदान करता है। उन्हें एर्डोस-रेनी मॉडल ''G''(''n'',''M'') के सामान्यीकरण के रूप में देखा जा सकता है। जब कंडीशनिंग जानकारी जरूरी नहीं कि किनारों की संख्या ''M'' हो। किन्तु जो भी <math>\mathcal{P}(G)</math> अन्य प्रकार से ग्राफ का गुण है। इस स्थिति में बहुत कम विश्लेषणात्मक परिणाम उपलब्ध हैं और औसत गुणों के अनुभवजन्य वितरण प्राप्त करने के लिए सिमुलेशन की आवश्यकता है।


== इतिहास ==
== इतिहास ==
रैंडम ग्राफ मॉडल का सबसे पहला उपयोग 1938 में [[हेलेन हॉल जेनिंग्स]] और [[ याकूब मोरेनो | याकूब मोरेनो]] द्वारा किया गया था, जहां यादृच्छिक मॉडल के साथ उनके नेटवर्क डेटा में पारस्परिक लिंक के अंश की तुलना करने के अध्ययन में एक चांस सोशियोग्राम (एक निर्देशित एर्दोस-रेनी मॉडल) पर विचार किया गया था।<ref>{{cite journal |last1=Moreno |first1=Jacob L |last2=Jennings |first2=Helen Hall |title=सामाजिक विन्यास के आँकड़े|journal=Sociometry |date=Jan 1938 |volume=1 |issue=3/4 |pages=342–374 |doi=10.2307/2785588|jstor=2785588 }}</ref> 1951 में [[रे सोलोमनॉफ]]़ और [[अनातोल रैपोपोर्ट]] द्वारा रेंडम नेट नाम के तहत एक और प्रयोग, निश्चित आउट-डिग्री के साथ निर्देशित ग्राफ़ के एक मॉडल का उपयोग करके और बेतरतीब ढंग से चुने गए अनुलग्नकों को अन्य कोने में किया गया था।<ref>{{cite journal |last1=Solomonoff |first1=Ray |last2=Rapoport |first2=Anatol |title=यादृच्छिक जाल की कनेक्टिविटी|journal=Bulletin of Mathematical Biophysics |date=June 1951 |volume=13 |issue=2 |pages=107–117 |doi=10.1007/BF02478357}}</ref>
रैंडम ग्राफ मॉडल का सबसे पहला उपयोग 1938 में [[हेलेन हॉल जेनिंग्स]] और [[ याकूब मोरेनो |याकूब मोरेनो]] द्वारा किया गया था। जहां यादृच्छिक मॉडल के साथ उनके नेटवर्क डेटा में पारस्परिक लिंक के अंश की तुलना करने के अध्ययन में एक चांस सोशियोग्राम (एक निर्देशित एर्दोस-रेनी मॉडल) पर विचार किया गया था।<ref>{{cite journal |last1=Moreno |first1=Jacob L |last2=Jennings |first2=Helen Hall |title=सामाजिक विन्यास के आँकड़े|journal=Sociometry |date=Jan 1938 |volume=1 |issue=3/4 |pages=342–374 |doi=10.2307/2785588|jstor=2785588 }}</ref> 1951 में [[रे सोलोमनॉफ]] और [[अनातोल रैपोपोर्ट]] द्वारा रेंडम नेट नाम के अऩुसार एक और प्रयोग निश्चित आउट-डिग्री के साथ निर्देशित ग्राफ़ के एक मॉडल का उपयोग करके और उत्कृष्ट प्रकार से चुने गए अनुलग्नकों को अन्य कोने में किया गया था।<ref>{{cite journal |last1=Solomonoff |first1=Ray |last2=Rapoport |first2=Anatol |title=यादृच्छिक जाल की कनेक्टिविटी|journal=Bulletin of Mathematical Biophysics |date=June 1951 |volume=13 |issue=2 |pages=107–117 |doi=10.1007/BF02478357}}</ref>
रैंडम ग्राफ़ के एर्डोस-रेनी मॉडल को पहली बार पॉल एर्दोस और अल्फ्रेड रेनी द्वारा उनके 1959 के पेपर ऑन रैंडम ग्राफ़ में परिभाषित किया गया था।<ref name="On Random Graphs">[[Paul Erdős|Erdős, P.]] [[Alfréd Rényi|Rényi, A]] (1959) "On Random Graphs I" in Publ. Math. Debrecen 6, p.&nbsp;290&ndash;297 [http://www.renyi.hu/~p_erdos/1959-11.pdf] {{Webarchive|url=https://web.archive.org/web/20200807021117/https://www.renyi.hu/~p_erdos/1959-11.pdf |date=2020-08-07 }}</ref> और स्वतंत्र रूप से गिल्बर्ट द्वारा अपने पेपर रैंडम ग्राफ़ में।<ref name="Random graphs">{{citation |last= Gilbert |first= E. N. |author-link=Edgar Gilbert|year=1959 |title=Random graphs |journal=Annals of Mathematical Statistics |volume= 30|issue= 4 |pages=1141–1144|doi=10.1214/aoms/1177706098 |doi-access=free }}.</ref>
 
रैंडम ग्राफ़ के एर्डोस-रेनी मॉडल को पहली बार पॉल एर्दोस और अल्फ्रेड रेनी द्वारा उनके 1959 के पेपर ऑन रैंडम ग्राफ़ में परिभाषित किया गया था<ref name="On Random Graphs">[[Paul Erdős|Erdős, P.]] [[Alfréd Rényi|Rényi, A]] (1959) "On Random Graphs I" in Publ. Math. Debrecen 6, p.&nbsp;290&ndash;297 [http://www.renyi.hu/~p_erdos/1959-11.pdf] {{Webarchive|url=https://web.archive.org/web/20200807021117/https://www.renyi.hu/~p_erdos/1959-11.pdf |date=2020-08-07 }}</ref> और स्वतंत्र रूप से गिल्बर्ट द्वारा अपने पेपर रैंडम ग्राफ़ में भी इसका प्रयोग किया गया था।<ref name="Random graphs">{{citation |last= Gilbert |first= E. N. |author-link=Edgar Gilbert|year=1959 |title=Random graphs |journal=Annals of Mathematical Statistics |volume= 30|issue= 4 |pages=1141–1144|doi=10.1214/aoms/1177706098 |doi-access=free }}.</ref>
 




Line 83: Line 88:
* [[अन्योन्याश्रित नेटवर्क]]
* [[अन्योन्याश्रित नेटवर्क]]
* [[ नेटवर्क विज्ञान | नेटवर्क विज्ञान]]
* [[ नेटवर्क विज्ञान | नेटवर्क विज्ञान]]
* [[ टपकन | टपकन]]
* [[ टपकन | रसना]]
* परकोलेशन थ्योरी
* परकोलेशन थ्योरी
* जेलेशन का रैंडम ग्राफ थ्योरी
* जेलेशन का रैंडम ग्राफ थ्योरी
Line 98: Line 103:


{{DEFAULTSORT:Random Graph}}
{{DEFAULTSORT:Random Graph}}
[[Category: ग्राफ सिद्धांत]]
[[index.php?title=Category:यादृच्छिक रेखांकन|*]]  
[[index.php?title=Category:यादृच्छिक रेखांकन|*]]


[[Category: Machine Translated Page]]
[[Category:Articles with hatnote templates targeting a nonexistent page|Random Graph]]
[[Category:Created On 21/03/2023]]
[[Category:Collapse templates|Random Graph]]
[[Category:Created On 21/03/2023|Random Graph]]
[[Category:Lua-based templates|Random Graph]]
[[Category:Machine Translated Page|Random Graph]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists|Random Graph]]
[[Category:Pages with reference errors]]
[[Category:Pages with script errors|Random Graph]]
[[Category:Short description with empty Wikidata description|Random Graph]]
[[Category:Sidebars with styles needing conversion|Random Graph]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready|Random Graph]]
[[Category:Templates generating microformats|Random Graph]]
[[Category:Templates that add a tracking category|Random Graph]]
[[Category:Templates that are not mobile friendly|Random Graph]]
[[Category:Templates that generate short descriptions|Random Graph]]
[[Category:Templates using TemplateData|Random Graph]]
[[Category:Webarchive template wayback links]]
[[Category:Wikipedia metatemplates|Random Graph]]
[[Category:ग्राफ सिद्धांत|Random Graph]]

Latest revision as of 09:43, 10 April 2023

For गिनती-अनंत यादृच्छिक ग्राफ, see राडो ग्राफ.
a series का हिस्सा चालू
नेटवर्क विज्ञान
Internet_map_1024.jpg
नेटवर्क प्रकार
ग्राफ
विशेषताएं
प्रकार
मॉडल
टोपोलॉजी
गतिकी
  • Lists
  • Categories

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

मॉडल

यादृच्छिक ग्राफ n अलग-अलग कोने के समूह से प्रारम्भ करके और यादृच्छिक रूप से उनके बीच क्रमिक किनारों को जोड़कर प्राप्त किया जाता है। इस क्षेत्र में अध्ययन का उद्देश्य यह निर्धारित करना है कि ग्राफ की एक विशेष गुण किस स्तर पर उत्पन्न होने की संभावना है।[3] अलग-अलग यादृच्छिक ग्राफ़ मॉडल ग्राफ़ पर अलग-अलग संभाव्यता वितरण उत्पन्न करते हैं। एडगर गिल्बर्ट द्वारा प्रस्तावित सबसे सामान्यतः अध्ययन किया जाने वाला है। जिसे G(n,p) निरूपित किया गया है। जिसमें प्रत्येक संभावित बढ़त स्वतंत्र रूप से प्रायिकता 0 < p < 1 के साथ होती है। m किनारों के साथ किसी एक विशेष यादृच्छिक ग्राफ को प्राप्त करने की प्रायिकता है।[4]

एक निकटतम संबंधित मॉडल एर्डोस-रेनी मॉडल G(n,M) को दर्शाता है। बिल्कुल M किनारों वाले सभी ग्राफों के लिए समान संभावना प्रदान करता है। 0 ≤ M ≤ N के साथ G(n,M) है। तत्व और प्रत्येक तत्व प्रायिकता के साथ होता है।[3] बाद वाले मॉडल को 'यादृच्छिक ग्राफ प्रक्रिया' के एक विशेष समय (M) पर एक स्नैपशॉट के रूप में देखा जा सकता है। , जो एक अनेक संभावनाओं में से चुनी हूई प्रक्रिया है। जो n कोने और बिना किनारों से प्रारम्भ होती है और प्रत्येक चरण में किनारों के समूह से समान रूप से चुने गए नए किनारे को जोड़ती है।

यदि इसके अतिरिक्त हम वर्टिकल के अनंत समूह के साथ प्रारम्भ करते हैं और फिर से प्रत्येक संभावित किनारे को प्रायिकता 0 <p <1 के साथ स्वतंत्र रूप से होने देते हैं। तो हमें एक वस्तु G मिलती है। जिसे 'अनंत यादृच्छिक ग्राफ' कहा जाता है। कुछ स्थितियों को छोड़कर जहां p, 0 या 1 के बीच में है। ऐसे G में लगभग निश्चित रूप से निम्नलिखित गुण होती है:

कोई भी n + m तत्व दिया गया है , V में एक शीर्ष c है। जो प्रत्येक के निकट है और किसी के निकट नहीं है।

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

एक अन्य मॉडल, जो गिल्बर्ट के यादृच्छिक ग्राफ मॉडल का सामान्यीकरण करता है, यादृच्छिक डॉट-उत्पाद मॉडल है। यादृच्छिक डॉट-उत्पाद ग्राफ प्रत्येक शीर्ष के साथ एक रियल वेक्टर को जोड़ता है। किसी भी कोने u और v के बीच किनारे uv की संभावना उनके संबंधित वैक्टर के डॉट प्रोडक्ट u • v का कार्य है।

नेटवर्क संभाव्यता मैट्रिक्स किनारे की संभावनाओं के माध्यम से यादृच्छिक रेखांकन करता है। जो संभावना का प्रतिनिधित्व करता है। वह दिया हुआ किनारा एक निर्दिष्ट समय अवधि के लिए उपस्थित है। यह मॉडल निर्देशित और अप्रत्यक्ष रूप से एक्स्टेंसिबल है; भारित और भारित और स्थिर या गतिशील रेखांकन संरचना भी उस्थित होता है।

M ≃ pN के लिए, जहां N संभव किनारों की अधिकतम संख्या है, दो सबसे व्यापक रूप से प्रयोग किए जाने वाले मॉडल, G(n,M) और G(n,p) लगभग विनिमेय हैं।[5]

यादृच्छिक नियमित ग्राफ एक विशेष स्थिति बनाते हैं। ऐसे गुणों के साथ जो सामान्य रूप से रैंडम ग्राफ़ से भिन्न हो सकते हैं।

एक बार जब हमारे पास यादृच्छिक ग्राफ़ का एक मॉडल होता है। तो ग्राफ़ पर प्रत्येक फलन यादृच्छिक चर बन जाता है। इस मॉडल का अध्ययन यह निर्धारित करने के लिए है कि क्या या कम से कम संभावना का अनुमान है कि एक गुण हो सकती है।[4]


शब्दावली

यादृच्छिक ग्राफ के संदर्भ में 'लगभग प्रत्येक' शब्द रिक्त स्थान और संभावनाओं के अनुक्रम को संदर्भित करता है। जैसे कि त्रुटि संभावना शून्य हो जाती है।[4]


गुण

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

परकोलेशन ग्राफ की दृढ़ता से संबंधित है (जिसे नेटवर्क भी कहा जाता है)। नोड्स का एक यादृच्छिक ग्राफ दिया और औसत डिग्री है। अगला हम भिन्न के नोड्स को हटाते हैं और केवल एक भिन्न छोड़ देत हैं। एक महत्वपूर्ण रिसाव सीमा उपस्थित है। जिसके नीचे ऊपर रहते हुए नेटवर्क टूट जाता है और एक बड़ा जुड़ा हुआ घटक उपस्थित है।[6][5][7][8][9]

स्थानीयकृत परकोलेशन एक नोड को उसके निकटम अगले निकटतम आदि को एक भिन्न तक हटाने के लिए संदर्भित करता है। जब तक नेटवर्क से नोड्स हटा दिए जाते हैं। यह दिखाया गया था कि डिग्री के पॉसों वितरण के साथ यादृच्छिक ग्राफ के लिए बिल्कुल यादृच्छिक हटाने के लिए भी उपस्थित है।

संभाव्यता पद्धति में रैंडम ग्राफ़ का व्यापक रूप से उपयोग किया जाता है। जहाँ कोई कुछ गुणों वाले ग्राफ़ के अस्तित्व को सिद्ध करने का प्रयास करता है। यादृच्छिक ग्राफ पर एक गुण का अस्तित्व अधिकांशतः ज़ेमेरीडी नियमितता लेम्मा के माध्यम से लगभग सभी ग्राफों पर उस गुण के अस्तित्व का संकेत दे सकता है।

यादृच्छिक नियमित रेखांकन में का समूह हैं, -नियमित रेखांकन के साथ ऐसा है कि और प्राकृतिक संख्या हैं और , और सम है।[3]

एक ग्राफ का डिग्री अनुक्रम में समूह में केवल किनारों की संख्या पर निर्भर करता है[3]

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

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

कुछ स्थिर के लिए , लगभग प्रत्येक लेबल वाले ग्राफ़ के साथ शिखर और कम से कम किनारों हैमिल्टनियन चक्र है। प्रायिकता 1 की ओर अग्रसर होने के साथ वह विशेष किनारा, जो न्यूनतम डिग्री को 2 तक बढ़ाता है और ग्राफ को हैमिल्टनियन बनाता है।

यादृच्छिक ग्राफ के गुण ग्राफ परिवर्तनों के अऩुसार बदल सकते हैं या अपरिवर्तित रह सकते हैं। उदाप्रत्येकण के लिए, अलिर्ज़ा माशघी | मशघी ए. एट अल। ने प्रदर्शित किया कि एक परिवर्तन जो यादृच्छिक ग्राफ़ को उनके किनारे-दोप्रत्येके ग्राफ़ (या लाइन ग्राफ़) में परिवर्तित करता है, लगभग समान डिग्री वितरण के साथ ग्राफ़ का एक समूह बनाता है। किन्तु डिग्री सहसंबंध और अधिक उच्च क्लस्टरिंग गुणांक के साथ इसका प्रयोग किया जाता है।[10]


रंग

शीर्ष V (G) = {1, ..., n} के साथ ऑर्डर n के एक यादृच्छिक ग्राफ G को देखते हुए रंगों की संख्या पर एल्गोरिथ्म द्वारा रंगों को 1, 2, ... रंगों से रंगा जा सकता है। (शीर्ष 1 रंगीन 1 है, शीर्ष 2 रंगीन 1 है। यदि यह शीर्ष 1 के निकट नहीं है। अन्यथा यह 2 रंगीन है, आदि)।[3] कई q रंगों को दिए गए यादृच्छिक ग्राफ़ के उचित रंगों की संख्या, जिसे इसके रंगीन बहुपद कहा जाता है, अब तक अज्ञात है। पैरामीटर n और किनारों की संख्या m या कनेक्शन प्रायिकता p के साथ यादृच्छिक ग्राफ़ के रंगीन बहुपद के शून्य के स्केलिंग को सांकेतिक पैटर्न मिलान के आधार पर एक एल्गोरिथ्म का उपयोग करके अनुभवजन्य रूप से अध्ययन किया गया है।[11]


रैंडम पेड़

Main article: सामान्य पेड़़

एक रैंडम ट्रीप एक ट्री (ग्राफ थ्योरी) या आर्बोरेसेंस (ग्राफ थ्योरी) है। जो एक स्टोचैस्टिक प्रक्रिया द्वारा बनता है। क्रम n और आकार M(n) के यादृच्छिक रेखांकन की एक बड़ी श्रृंखला में क्रम k के ट्री घटकों की संख्या का वितरण विषम रूप से पॉइसन वितरण है। रैंडम ट्री के प्रकारों में यूनिफॉर्म स्पैनिंग ट्री, रैंडम मिनिमम स्पैनिंग ट्री, रैंडम बाइनरी ट्री, ट्रैप, तेजी से रैंडम ट्री, ब्राउनियन ट्री और रैंडम फॉरेस्ट सम्मिलित हैं।

नियमानुसार यादृच्छिक रेखांकन

संभाव्यता स्थान पर परिभाषित दिए गए यादृच्छिक ग्राफ मॉडल पर विचार करें और एक वास्तविक मूल्यवान फलन बनें। जो प्रत्येक ग्राफ़ में m गुणों के वेक्टर को निर्दिष्ट करता है।

एक निश्चित के लिए सशर्त यादृच्छिक रेखांकन वे मॉडल हैं। जिनमें संभाव्यता मापी जाती है। सभी ग्राफों को शून्य प्रायिकता प्रदान करता है जैसे कि '.

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

इतिहास

रैंडम ग्राफ मॉडल का सबसे पहला उपयोग 1938 में हेलेन हॉल जेनिंग्स और याकूब मोरेनो द्वारा किया गया था। जहां यादृच्छिक मॉडल के साथ उनके नेटवर्क डेटा में पारस्परिक लिंक के अंश की तुलना करने के अध्ययन में एक चांस सोशियोग्राम (एक निर्देशित एर्दोस-रेनी मॉडल) पर विचार किया गया था।[12] 1951 में रे सोलोमनॉफ और अनातोल रैपोपोर्ट द्वारा रेंडम नेट नाम के अऩुसार एक और प्रयोग निश्चित आउट-डिग्री के साथ निर्देशित ग्राफ़ के एक मॉडल का उपयोग करके और उत्कृष्ट प्रकार से चुने गए अनुलग्नकों को अन्य कोने में किया गया था।[13]

रैंडम ग्राफ़ के एर्डोस-रेनी मॉडल को पहली बार पॉल एर्दोस और अल्फ्रेड रेनी द्वारा उनके 1959 के पेपर ऑन रैंडम ग्राफ़ में परिभाषित किया गया था[9] और स्वतंत्र रूप से गिल्बर्ट द्वारा अपने पेपर रैंडम ग्राफ़ में भी इसका प्रयोग किया गया था।[7]


यह भी देखें

संदर्भ

  1. ↑ Bollobás, Béla (2001). यादृच्छिक रेखांकन (2nd ed.). Cambridge University Press.
  2. ↑ Frieze, Alan; Karonski, Michal (2015). यादृच्छिक रेखांकन का परिचय. Cambridge University Press.
  3. ↑ 3.0 3.1 3.2 3.3 3.4 3.5 Béla Bollobás, Random Graphs, 1985, Academic Press Inc., London Ltd.
  4. ↑ 4.0 4.1 4.2 Béla Bollobás, Probabilistic Combinatorics and Its Applications, 1991, Providence, RI: American Mathematical Society.
  5. ↑ 5.0 5.1 Bollobas, B. and Riordan, O.M. "Mathematical results on scale-free random graphs" in "Handbook of Graphs and Networks" (S. Bornholdt and H.G. Schuster (eds)), Wiley VCH, Weinheim, 1st ed., 2003
  6. ↑ Cite error: Invalid <ref> tag; no text was provided for refs named Random Graphs
  7. ↑ 7.0 7.1 Gilbert, E. N. (1959), "Random graphs", Annals of Mathematical Statistics, 30 (4): 1141–1144, doi:10.1214/aoms/1177706098.
  8. ↑ Newman, M. E. J. (2010). Networks: An Introduction. Oxford.
  9. ↑ 9.0 9.1 Erdős, P. Rényi, A (1959) "On Random Graphs I" in Publ. Math. Debrecen 6, p. 290–297 [1] Archived 2020-08-07 at the Wayback Machine
  10. ↑ Ramezanpour, A.; Karimipour, V.; Mashaghi, A. (2003). "असंबद्ध नेटवर्क से सहसंबद्ध नेटवर्क बनाना". Phys. Rev. E. 67 (46107): 046107. arXiv:cond-mat/0212469. Bibcode:2003PhRvE..67d6107R. doi:10.1103/PhysRevE.67.046107. PMID 12786436. S2CID 33054818.
  11. ↑ Van Bussel, Frank; Ehrlich, Christoph; Fliegner, Denny; Stolzenberg, Sebastian; Timme, Marc (2010). "यादृच्छिक रेखांकन के रंगीन बहुपद". J. Phys. A: Math. Theor. 43 (17): 175002. arXiv:1709.06209. Bibcode:2010JPhA...43q5002V. doi:10.1088/1751-8113/43/17/175002. S2CID 15723612.
  12. ↑ Moreno, Jacob L; Jennings, Helen Hall (Jan 1938). "सामाजिक विन्यास के आँकड़े". Sociometry. 1 (3/4): 342–374. doi:10.2307/2785588. JSTOR 2785588.
  13. ↑ Solomonoff, Ray; Rapoport, Anatol (June 1951). "यादृच्छिक जाल की कनेक्टिविटी". Bulletin of Mathematical Biophysics. 13 (2): 107–117. doi:10.1007/BF02478357.


*

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=यादृच्छिक_ग्राफ&oldid=124187’