ग्राफ गणना: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
[[File:Cayley's formula 2-4.svg|thumb|की पूरी सूची | [[File:Cayley's formula 2-4.svg|thumb|की पूरी सूची | ||
सभी ट्री (ग्राफ सिद्धांत)#रूटेड ट्री 2, 3, और 4 लेबल वाले शीर्षों पर: <math>2^{2-2}=1</math> 2 शीर्षों वाला वृक्ष, | सभी ट्री (ग्राफ सिद्धांत)#रूटेड ट्री 2, 3, और 4 लेबल वाले शीर्षों पर: <math>2^{2-2}=1</math> 2 शीर्षों वाला वृक्ष, | ||
<math>3^{3-2}=3</math> 3 शीर्षों वाले ट्री, और <math>4^{4-2}=16</math> 4 शीर्षों वाले वृक्ष।]][[साहचर्य|संयोजक]] में, गणित का | <math>3^{3-2}=3</math> 3 शीर्षों वाले ट्री, और <math>4^{4-2}=16</math> 4 शीर्षों वाले वृक्ष।]][[साहचर्य|संयोजक]] में, गणित का क्षेत्र, '''ग्राफ़ गणना''', [[संयुक्त गणना]] समस्याओं के वर्ग का वर्णन करता है जिसमें किसी को [[अप्रत्यक्ष ग्राफ]] या कुछ प्रकार के [[निर्देशित ग्राफ]] की गणना करनी चाहिए, सामान्यतः ग्राफ़ के शीर्षों की संख्या के फ़ंक्शन के रूप में <ref>{{cite book | ||
|last1 = Harary | first1 = Frank | author1-link = Frank Harary | first2 = Edgar M. | last2 = Palmer | year = 1973| title = चित्रमय गणना| publisher = [[Academic Press]] | isbn = 0-12-324245-2}}</ref> इन समस्याओं को या तो बिल्कुल ([[बीजगणितीय गणना]] समस्या के रूप में) या [[स्पर्शोन्मुख विश्लेषण]] से हल किया जा सकता है। | |last1 = Harary | first1 = Frank | author1-link = Frank Harary | first2 = Edgar M. | last2 = Palmer | year = 1973| title = चित्रमय गणना| publisher = [[Academic Press]] | isbn = 0-12-324245-2}}</ref> इन समस्याओं को या तो बिल्कुल ([[बीजगणितीय गणना]] समस्या के रूप में) या [[स्पर्शोन्मुख विश्लेषण]] से हल किया जा सकता है। | ||
गणित के इस क्षेत्र में अग्रणी जॉर्ज पोल्या थे,<ref>Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Math. 68 (1937), 145-254</ref> [[आर्थर केली]] <ref>{{acad|id=CLY838A|name=Cayley, Arthur}}</ref> और जे. हावर्ड रेडफ़ील्ड है.<ref>The theory of group-reduced distributions. American J. Math. 49 (1927), 433-455.</ref> | गणित के इस क्षेत्र में अग्रणी जॉर्ज पोल्या थे,<ref>Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Math. 68 (1937), 145-254</ref> [[आर्थर केली]] <ref>{{acad|id=CLY838A|name=Cayley, Arthur}}</ref> और जे. हावर्ड रेडफ़ील्ड है.<ref>The theory of group-reduced distributions. American J. Math. 49 (1927), 433-455.</ref> | ||
==लेबल बनाम गैर-लेबल समस्याएँ== | ==लेबल बनाम गैर-लेबल समस्याएँ== | ||
कुछ ग्राफ़िकल गणना समस्याओं में, ग्राफ़ के शीर्षों को इस तरह से लेबल किया जाता है कि वे एक-दूसरे से अलग हो सकती है, जबकि अन्य समस्याओं में शीर्षों के किसी भी क्रमपरिवर्तन को | कुछ ग्राफ़िकल गणना समस्याओं में, ग्राफ़ के शीर्षों को इस तरह से लेबल किया जाता है कि वे एक-दूसरे से अलग हो सकती है, जबकि अन्य समस्याओं में शीर्षों के किसी भी क्रमपरिवर्तन को ही ग्राफ़ बनाने के लिए माना जाता है, इसलिए शीर्षों पर विचार किया जाता है समान या बिना लेबल वाला होता है। सामान्यतः, लेबल की गई समस्याएं सरल होती हैं।<ref>Harary and Palmer, p. 1.</ref> सामान्यतः संयोजन गणना के साथ, पोल्या गणना प्रमेय लेबल रहित समस्याओं को कम करके लेबल वाली समस्याओं में बदलने के लिए महत्वपूर्ण उपकरण है: प्रत्येक लेबल रहित वर्ग को लेबल की गई वस्तुओं के समरूपता वर्ग के रूप में माना जाता है। | ||
==स्पष्ट गणना सूत्र == | ==स्पष्ट गणना सूत्र == | ||
| Line 13: | Line 11: | ||
*लेबल 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> | ||
*लेबल n-वर्टेक्स [[सरल निर्देशित ग्राफ]] की संख्या 2<sup>n(n −1)</sup> है.<ref>Harary and Palmer, p. 5.</ref> | *लेबल n-वर्टेक्स [[सरल निर्देशित ग्राफ]] की संख्या 2<sup>n(n −1)</sup> है.<ref>Harary and Palmer, p. 5.</ref> | ||
*संख्या C<sub>n</sub>n वर्टेक्स लेबल वाले [[ जुड़ा हुआ ग्राफ़ | संबद्ध ग्राफ़]] | *संख्या C<sub>n</sub>n वर्टेक्स लेबल वाले [[ जुड़ा हुआ ग्राफ़ |संबद्ध ग्राफ़]] के अप्रत्यक्ष ग्राफ़ [[पुनरावृत्ति संबंध]] को संतुष्ट करते हैं <ref>Harary and Palmer, p. 7.</ref> | ||
::<math>C_n=2^{n\choose 2} - \frac{1}{n}\sum_{k=1}^{n-1} k{n\choose k} 2^{n-k\choose 2} C_k.</math> | ::<math>C_n=2^{n\choose 2} - \frac{1}{n}\sum_{k=1}^{n-1} k{n\choose k} 2^{n-k\choose 2} C_k.</math> | ||
:जिससे कोई सरली से गणना कर सकता है, n = 1, 2, 3, ... के लिए, कि C<sub>n</sub> के लिए मान हैं | :जिससे कोई सरली से गणना कर सकता है, n = 1, 2, 3, ... के लिए, कि C<sub>n</sub> के लिए मान हैं | ||
| Line 31: | 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> | ||
== ग्राफ़ डेटाबेस == | == ग्राफ़ डेटाबेस == | ||
Revision as of 15:22, 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.
