ग्राफ गणना

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

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

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

बल रहित वर्ग को लेबल

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

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

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

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

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

$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)

• लेबल n-वर्टेक्स ट्री (ग्राफ सिद्धांत) रूटेड ट्री की संख्या nⁿ⁻² है (केली का सूत्र)।
• बिना लेबल वाले n-वर्टेक्स कैटरपिलर ट्री की संख्या है

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

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

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

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