ग्राफ गणना: Difference between revisions
No edit summary |
No edit summary |
||
| Line 7: | Line 7: | ||
कुछ ग्राफ़िकल गणना समस्याओं में, ग्राफ़ के शीर्षों को इस तरह से लेबल किया जाता है कि वे एक-दूसरे से अलग हो सकती है, जबकि अन्य समस्याओं में शीर्षों के किसी भी क्रमपरिवर्तन को ही ग्राफ़ बनाने के लिए माना जाता है, इसलिए शीर्षों पर विचार किया जाता है समान या बिना लेबल वाला होता है। सामान्यतः, लेबल की गई समस्याएं सरल होती हैं।<ref>Harary and Palmer, p. 1.</ref> सामान्यतः संयोजन गणना के साथ, पोल्या गणना प्रमेय लेबल रहित समस्याओं को कम करके लेबल वाली समस्याओं में बदलने के लिए महत्वपूर्ण उपकरण है: प्रत्येक लेबल रहित वर्ग को लेबल की गई वस्तुओं के समरूपता वर्ग के रूप में माना जाता है। | कुछ ग्राफ़िकल गणना समस्याओं में, ग्राफ़ के शीर्षों को इस तरह से लेबल किया जाता है कि वे एक-दूसरे से अलग हो सकती है, जबकि अन्य समस्याओं में शीर्षों के किसी भी क्रमपरिवर्तन को ही ग्राफ़ बनाने के लिए माना जाता है, इसलिए शीर्षों पर विचार किया जाता है समान या बिना लेबल वाला होता है। सामान्यतः, लेबल की गई समस्याएं सरल होती हैं।<ref>Harary and Palmer, p. 1.</ref> सामान्यतः संयोजन गणना के साथ, पोल्या गणना प्रमेय लेबल रहित समस्याओं को कम करके लेबल वाली समस्याओं में बदलने के लिए महत्वपूर्ण उपकरण है: प्रत्येक लेबल रहित वर्ग को लेबल की गई वस्तुओं के समरूपता वर्ग के रूप में माना जाता है। | ||
==स्पष्ट गणना सूत्र | ==स्पष्ट गणना सूत्र == | ||
इस क्षेत्र में कुछ महत्वपूर्ण परिणामों में निम्नलिखित सम्मिलित हैं। | इस क्षेत्र में कुछ महत्वपूर्ण परिणामों में निम्नलिखित सम्मिलित हैं। | ||
*लेबल n-वर्टेक्स [[सरल ग्राफ]] की संख्या 2<sup>n(n −1)/2</sup> है.<ref>Harary and Palmer, p. 3.</ref> | *लेबल n-वर्टेक्स [[सरल ग्राफ]] की संख्या 2<sup>n(n −1)/2</sup> है.<ref>Harary and Palmer, p. 3.</ref> | ||
| Line 29: | Line 29: | ||
}}.</ref> | }}.</ref> | ||
::<math>2^{n-4}+2^{\lfloor (n-4)/2\rfloor}.</math> | ::<math>2^{n-4}+2^{\lfloor (n-4)/2\rfloor}.</math> | ||
== ग्राफ़ डेटाबेस | == ग्राफ़ डेटाबेस == | ||
विभिन्न अनुसंधान समूहों ने खोजने योग्य डेटाबेस प्रदान किया है जो छोटे आकार के कुछ गुणों वाले ग्राफ़ को सूचीबद्ध करता है। उदाहरण के लिए | विभिन्न अनुसंधान समूहों ने खोजने योग्य डेटाबेस प्रदान किया है जो छोटे आकार के कुछ गुणों वाले ग्राफ़ को सूचीबद्ध करता है। उदाहरण के लिए | ||
| Line 36: | Line 36: | ||
* [https://github.com/jasongrout/graph_database छोटा ग्राफ़ डेटाबेस] | * [https://github.com/jasongrout/graph_database छोटा ग्राफ़ डेटाबेस] | ||
==संदर्भ | ==संदर्भ == | ||
{{reflist|2}} | {{reflist|2}} | ||
[[Category: ग्राफ गणना| ग्राफ गणना]] [[Category: गणनात्मक संयोजक]] | [[Category: ग्राफ गणना| ग्राफ गणना]] [[Category: गणनात्मक संयोजक]] | ||
Revision as of 15:23, 7 July 2023
संयोजक में, गणित का क्षेत्र, ग्राफ़ गणना, संयुक्त गणना समस्याओं के वर्ग का वर्णन करता है जिसमें किसी को अप्रत्यक्ष ग्राफ या कुछ प्रकार के निर्देशित ग्राफ की गणना करनी चाहिए, सामान्यतः ग्राफ़ के शीर्षों की संख्या के फ़ंक्शन के रूप में [1] इन समस्याओं को या तो बिल्कुल (बीजगणितीय गणना समस्या के रूप में) या स्पर्शोन्मुख विश्लेषण से हल किया जा सकता है।
गणित के इस क्षेत्र में अग्रणी जॉर्ज पोल्या थे,[2] आर्थर केली [3] और जे. हावर्ड रेडफ़ील्ड है.[4]
लेबल बनाम गैर-लेबल समस्याएँ
कुछ ग्राफ़िकल गणना समस्याओं में, ग्राफ़ के शीर्षों को इस तरह से लेबल किया जाता है कि वे एक-दूसरे से अलग हो सकती है, जबकि अन्य समस्याओं में शीर्षों के किसी भी क्रमपरिवर्तन को ही ग्राफ़ बनाने के लिए माना जाता है, इसलिए शीर्षों पर विचार किया जाता है समान या बिना लेबल वाला होता है। सामान्यतः, लेबल की गई समस्याएं सरल होती हैं।[5] सामान्यतः संयोजन गणना के साथ, पोल्या गणना प्रमेय लेबल रहित समस्याओं को कम करके लेबल वाली समस्याओं में बदलने के लिए महत्वपूर्ण उपकरण है: प्रत्येक लेबल रहित वर्ग को लेबल की गई वस्तुओं के समरूपता वर्ग के रूप में माना जाता है।
स्पष्ट गणना सूत्र
इस क्षेत्र में कुछ महत्वपूर्ण परिणामों में निम्नलिखित सम्मिलित हैं।
- लेबल n-वर्टेक्स सरल ग्राफ की संख्या 2n(n −1)/2 है.[6]
- लेबल n-वर्टेक्स सरल निर्देशित ग्राफ की संख्या 2n(n −1) है.[7]
- संख्या Cnn वर्टेक्स लेबल वाले संबद्ध ग्राफ़ के अप्रत्यक्ष ग्राफ़ पुनरावृत्ति संबंध को संतुष्ट करते हैं [8]
- जिससे कोई सरली से गणना कर सकता है, n = 1, 2, 3, ... के लिए, कि Cn के लिए मान हैं
- लेबल n-वर्टेक्स ट्री (ग्राफ सिद्धांत) रूटेड ट्री की संख्या nn−2 है (केली का सूत्र)।
- बिना लेबल वाले n-वर्टेक्स कैटरपिलर ट्री की संख्या है [9]
ग्राफ़ डेटाबेस
विभिन्न अनुसंधान समूहों ने खोजने योग्य डेटाबेस प्रदान किया है जो छोटे आकार के कुछ गुणों वाले ग्राफ़ को सूचीबद्ध करता है। उदाहरण के लिए
संदर्भ
- ↑ Harary, Frank; Palmer, Edgar M. (1973). चित्रमय गणना. Academic Press. ISBN 0-12-324245-2.
- ↑ Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Math. 68 (1937), 145-254
- ↑ "Cayley, Arthur (CLY838A)". A Cambridge Alumni Database. University of Cambridge.
- ↑ The theory of group-reduced distributions. American J. Math. 49 (1927), 433-455.
- ↑ Harary and Palmer, p. 1.
- ↑ Harary and Palmer, p. 3.
- ↑ Harary and Palmer, p. 5.
- ↑ Harary and Palmer, p. 7.
- ↑ Harary, Frank; Schwenk, Allen J. (1973), "The number of caterpillars" (PDF), Discrete Mathematics, 6 (4): 359–365, doi:10.1016/0012-365x(73)90067-8, hdl:2027.42/33977.
