ग्राफ गणना: Difference between revisions

From Vigyanwiki
(Created page with "File:Cayley's formula 2-4.svg|thumb|की पूरी सूची सभी Tree_(graph_theory)#Rooted_tree 2, 3, और 4 लेबल वाले शीर्षों...")
 
m (8 revisions imported from alpha:ग्राफ_गणना)
 
(7 intermediate revisions by 2 users not shown)
Line 1: Line 1:
[[File:Cayley's formula 2-4.svg|thumb|की पूरी सूची
[[File:Cayley's formula 2-4.svg|thumb|की पूरी सूची
सभी Tree_(graph_theory)#Rooted_tree 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 शीर्षों वाले वृक्ष।]][[साहचर्य]] में, गणित का एक क्षेत्र, ग्राफ़ एन्यूमरेशन, [[संयुक्त गणना]] समस्याओं के एक वर्ग का वर्णन करता है जिसमें किसी को [[अप्रत्यक्ष ग्राफ]]़ या कुछ प्रकार के [[निर्देशित ग्राफ]]़ की गणना करनी चाहिए, आमतौर पर ग्राफ़ के शीर्षों की संख्या के एक फ़ंक्शन के रूप में।<ref>{{cite book
<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> सामान्यतः संयोजन गणना के साथ, पोल्या गणना प्रमेय लेबल रहित समस्याओं को कम करके लेबल वाली समस्याओं में बदलने के लिए महत्वपूर्ण उपकरण है: प्रत्येक लेबल रहित वर्ग को लेबल की गई वस्तुओं के समरूपता वर्ग के रूप में माना जाता है।


 
==स्पष्ट गणना सूत्र                                                                                                                         ==
==लेबल बनाम गैर-लेबल समस्याएँ==
इस क्षेत्र में कुछ महत्वपूर्ण परिणामों में निम्नलिखित सम्मिलित हैं।
कुछ ग्राफ़िकल गणना समस्याओं में, ग्राफ़ के शीर्षों को इस तरह से लेबल किया जाता है कि वे एक-दूसरे से अलग हो सकें, जबकि अन्य समस्याओं में शीर्षों के किसी भी क्रमपरिवर्तन को एक ही ग्राफ़ बनाने के लिए माना जाता है, इसलिए शीर्षों पर विचार किया जाता है समान या बिना लेबल वाला। सामान्य तौर पर, लेबल की गई समस्याएं आसान होती हैं।<ref>Harary and Palmer, p. 1.</ref> आम तौर पर संयोजन गणना के साथ, पोल्या गणना प्रमेय लेबल रहित समस्याओं को कम करके लेबल वाली समस्याओं में बदलने के लिए एक महत्वपूर्ण उपकरण है: प्रत्येक लेबल रहित वर्ग को लेबल की गई वस्तुओं के समरूपता वर्ग के रूप में माना जाता है।
*लेबल n-वर्टेक्स [[सरल ग्राफ]] की संख्या 2<sup>n(n&hairsp;−1)/2</sup> है.<ref>Harary and Palmer, p. 3.</ref>
 
*लेबल n-वर्टेक्स [[सरल निर्देशित ग्राफ]] की संख्या 2<sup>n(n&hairsp;−1)</sup> है.<ref>Harary and Palmer, p. 5.</ref>
==सटीक गणना सूत्र==
*संख्या C<sub>n</sub>n वर्टेक्स लेबल वाले [[ जुड़ा हुआ ग्राफ़ |संबद्ध ग्राफ़]] के अप्रत्यक्ष ग्राफ़ [[पुनरावृत्ति संबंध]] को संतुष्ट करते हैं <ref>Harary and Palmer, p. 7.</ref>
इस क्षेत्र में कुछ महत्वपूर्ण परिणामों में निम्नलिखित शामिल हैं।
*लेबल एन-वर्टेक्स [[सरल ग्राफ]] की संख्या 2 है<sup>n(n&hairsp;−1)/2</sup>.<ref>Harary and Palmer, p. 3.</ref>
*लेबल एन-वर्टेक्स [[सरल निर्देशित ग्राफ]]़ की संख्या 2 है<sup>n(n&hairsp;−1)</sup>.<ref>Harary and Palmer, p. 5.</ref>
*संख्या सी<sub>n</sub>एन-वर्टेक्स लेबल वाले [[ जुड़ा हुआ ग्राफ़ ]]़ के अप्रत्यक्ष ग्राफ़ [[पुनरावृत्ति संबंध]] को संतुष्ट करते हैं<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> के लिए मान हैं
::1, 1, 4, 38, 728, 26704, 1866256, ...{{OEIS|id=A001187}}
::1, 1, 4, 38, 728, 26704, 1866256, ...{{OEIS|id=A001187}}
*लेबल एन-वर्टेक्स ट्री_(ग्राफ_थ्योरी)#रूटेड_ट्री की संख्या एन है<sup>n−2</sup> (केली का सूत्र)।
*लेबल n-वर्टेक्स ट्री (ग्राफ सिद्धांत) रूटेड ट्री की संख्या n<sup>n−2</sup> है (केली का सूत्र)।
*बिना लेबल वाले एन-वर्टेक्स कैटरपिलर पेड़ की संख्या है<ref>{{citation
*बिना लेबल वाले 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 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>
 
== ग्राफ़ डेटाबेस                                                                                                                                                                                           ==
 
== ग्राफ़ डेटाबेस ==


विभिन्न अनुसंधान समूहों ने खोजने योग्य डेटाबेस प्रदान किया है जो छोटे आकार के कुछ गुणों वाले ग्राफ़ को सूचीबद्ध करता है। उदाहरण के लिए
विभिन्न अनुसंधान समूहों ने खोजने योग्य डेटाबेस प्रदान किया है जो छोटे आकार के कुछ गुणों वाले ग्राफ़ को सूचीबद्ध करता है। उदाहरण के लिए
Line 40: Line 36:
* [https://github.com/jasongrout/graph_database छोटा ग्राफ़ डेटाबेस]
* [https://github.com/jasongrout/graph_database छोटा ग्राफ़ डेटाबेस]


==संदर्भ==
==संदर्भ                                                                                                                                                                                                             ==
{{reflist|2}}
{{reflist|2}}
[[Category: ग्राफ गणना| ग्राफ गणना]] [[Category: गणनात्मक संयोजक]]  
[[Category: ग्राफ गणना| ग्राफ गणना]] [[Category: गणनात्मक संयोजक]]  
Line 48: Line 44:
[[Category: Machine Translated Page]]
[[Category: Machine Translated Page]]
[[Category:Created On 27/06/2023]]
[[Category:Created On 27/06/2023]]
[[Category:Vigyan Ready]]

Latest revision as of 07:01, 8 October 2023

की पूरी सूची सभी ट्री (ग्राफ सिद्धांत)#रूटेड ट्री 2, 3, और 4 लेबल वाले शीर्षों पर: 2 शीर्षों वाला वृक्ष, 3 शीर्षों वाले ट्री, और 4 शीर्षों वाले वृक्ष।

संयोजक में, गणित का क्षेत्र, ग्राफ़ गणना, संयुक्त गणना समस्याओं के वर्ग का वर्णन करता है जिसमें किसी को अप्रत्यक्ष ग्राफ या कुछ प्रकार के निर्देशित ग्राफ की गणना करनी चाहिए, सामान्यतः ग्राफ़ के शीर्षों की संख्या के फ़ंक्शन के रूप में [1] इन समस्याओं को या तो बिल्कुल (बीजगणितीय गणना समस्या के रूप में) या स्पर्शोन्मुख विश्लेषण से हल किया जा सकता है।

गणित के इस क्षेत्र में अग्रणी जॉर्ज पोल्या थे,[2] आर्थर केली [3] और जे. हावर्ड रेडफ़ील्ड है.[4]

लेबल बनाम गैर-लेबल समस्याएँ

कुछ ग्राफ़िकल गणना समस्याओं में, ग्राफ़ के शीर्षों को इस तरह से लेबल किया जाता है कि वे एक-दूसरे से अलग हो सकती है, जबकि अन्य समस्याओं में शीर्षों के किसी भी क्रमपरिवर्तन को ही ग्राफ़ बनाने के लिए माना जाता है, इसलिए शीर्षों पर विचार किया जाता है समान या बिना लेबल वाला होता है। सामान्यतः, लेबल की गई समस्याएं सरल होती हैं।[5] सामान्यतः संयोजन गणना के साथ, पोल्या गणना प्रमेय लेबल रहित समस्याओं को कम करके लेबल वाली समस्याओं में बदलने के लिए महत्वपूर्ण उपकरण है: प्रत्येक लेबल रहित वर्ग को लेबल की गई वस्तुओं के समरूपता वर्ग के रूप में माना जाता है।

स्पष्ट गणना सूत्र

इस क्षेत्र में कुछ महत्वपूर्ण परिणामों में निम्नलिखित सम्मिलित हैं।

जिससे कोई सरली से गणना कर सकता है, n = 1, 2, 3, ... के लिए, कि Cn के लिए मान हैं
1, 1, 4, 38, 728, 26704, 1866256, ...(sequence A001187 in the OEIS)
  • लेबल n-वर्टेक्स ट्री (ग्राफ सिद्धांत) रूटेड ट्री की संख्या nn−2 है (केली का सूत्र)।
  • बिना लेबल वाले n-वर्टेक्स कैटरपिलर ट्री की संख्या है [9]

ग्राफ़ डेटाबेस

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

संदर्भ

  1. ↑ Harary, Frank; Palmer, Edgar M. (1973). चित्रमय गणना. Academic Press. ISBN 0-12-324245-2.
  2. ↑ Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Math. 68 (1937), 145-254
  3. ↑ "Cayley, Arthur (CLY838A)". A Cambridge Alumni Database. University of Cambridge.
  4. ↑ The theory of group-reduced distributions. American J. Math. 49 (1927), 433-455.
  5. ↑ Harary and Palmer, p. 1.
  6. ↑ Harary and Palmer, p. 3.
  7. ↑ Harary and Palmer, p. 5.
  8. ↑ Harary and Palmer, p. 7.
  9. ↑ 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.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=ग्राफ_गणना&oldid=263529’