ग्राफ गणना: Difference between revisions
From Vigyanwiki
(Created page with "File:Cayley's formula 2-4.svg|thumb|की पूरी सूची सभी Tree_(graph_theory)#Rooted_tree 2, 3, और 4 लेबल वाले शीर्षों...") |
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 शीर्षों वाला वृक्ष, | ||
<math>3^{3-2}=3</math> 3 शीर्षों वाले | <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> सामान्यतः संयोजन गणना के साथ, पोल्या गणना प्रमेय लेबल रहित समस्याओं को कम करके लेबल वाली समस्याओं में बदलने के लिए एक महत्वपूर्ण उपकरण है: प्रत्येक लेबल रहित वर्ग को लेबल की गई वस्तुओं के समरूपता वर्ग के रूप में माना जाता है। | ||
== | ==स्पष्ट गणना सूत्र == | ||
इस क्षेत्र में कुछ महत्वपूर्ण परिणामों में निम्नलिखित | इस क्षेत्र में कुछ महत्वपूर्ण परिणामों में निम्नलिखित सम्मिलित हैं। | ||
*लेबल | *लेबल 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> | ||
*संख्या | *संख्या 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> के लिए मान हैं | ||
::1, 1, 4, 38, 728, 26704, 1866256, ...{{OEIS|id=A001187}} | ::1, 1, 4, 38, 728, 26704, 1866256, ...{{OEIS|id=A001187}} | ||
*लेबल | *लेबल n-वर्टेक्स ट्री (ग्राफ सिद्धांत) रूटेड ट्री की संख्या n<sup>n−2</sup> है (केली का सूत्र)। | ||
*बिना लेबल वाले | *बिना लेबल वाले n-वर्टेक्स कैटरपिलर ट्री की संख्या है <ref>{{citation | ||
| last1 = Harary | first1 = Frank | author1-link = Frank Harary | | last1 = Harary | first1 = Frank | author1-link = Frank Harary | ||
| last2 = Schwenk | first2 = Allen J. | | last2 = Schwenk | first2 = Allen J. | ||
| Line 33: | Line 33: | ||
== ग्राफ़ डेटाबेस == | == ग्राफ़ डेटाबेस == | ||
विभिन्न अनुसंधान समूहों ने खोजने योग्य डेटाबेस प्रदान किया है जो छोटे आकार के कुछ गुणों वाले ग्राफ़ को सूचीबद्ध करता है। उदाहरण के लिए | विभिन्न अनुसंधान समूहों ने खोजने योग्य डेटाबेस प्रदान किया है जो छोटे आकार के कुछ गुणों वाले ग्राफ़ को सूचीबद्ध करता है। उदाहरण के लिए | ||
| Line 40: | Line 40: | ||
* [https://github.com/jasongrout/graph_database छोटा ग्राफ़ डेटाबेस] | * [https://github.com/jasongrout/graph_database छोटा ग्राफ़ डेटाबेस] | ||
==संदर्भ== | ==संदर्भ == | ||
{{reflist|2}} | {{reflist|2}} | ||
[[Category: ग्राफ गणना| ग्राफ गणना]] [[Category: गणनात्मक संयोजक]] | [[Category: ग्राफ गणना| ग्राफ गणना]] [[Category: गणनात्मक संयोजक]] | ||
Revision as of 15:21, 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.
