ग्राफ गणना

की पूरी सूची सभी Tree_(graph_theory)#Rooted_tree 2, 3, और 4 लेबल वाले शीर्षों पर: $2^{2-2}=1$ 2 शीर्षों वाला वृक्ष, $3^{3-2}=3$ 3 शीर्षों वाले पेड़, और $4^{4-2}=16$ 4 शीर्षों वाले वृक्ष।

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

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

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

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

सटीक गणना सूत्र

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

• लेबल एन-वर्टेक्स सरल ग्राफ की संख्या 2 है^{n(n −1)/2}.
• लेबल एन-वर्टेक्स सरल निर्देशित ग्राफ़ की संख्या 2 है^n(n −1).
• संख्या सी_nएन-वर्टेक्स लेबल वाले जुड़ा हुआ ग्राफ़ ़ के अप्रत्यक्ष ग्राफ़ पुनरावृत्ति संबंध को संतुष्ट करते हैं

$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}.$

जिससे कोई आसानी से गणना कर सकता है, n = 1, 2, 3, ... के लिए, कि C के लिए मान_nहैं

1, 1, 4, 38, 728, 26704, 1866256, ...(sequence A001187 in the OEIS)

• लेबल एन-वर्टेक्स ट्री_(ग्राफ_थ्योरी)#रूटेड_ट्री की संख्या एन हैⁿ⁻² (केली का सूत्र)।
• बिना लेबल वाले एन-वर्टेक्स कैटरपिलर पेड़ की संख्या है

$2^{n-4}+2^{\lfloor (n-4)/2\rfloor }.$

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

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

• ग्राफ़ का घर
• छोटा ग्राफ़ डेटाबेस