Graph enumeration
مجموعہیات میں، ریاضی کا ایک شعبہ، گراف گنتی مشترکہ گنتی کے مسائل کی ایک کلاس کو بیان کرتا ہے جس میں کسی کو مخصوص اقسام کے غیر ہدایت شدہ یا ہدایت شدہ گرافوں کو شمار کرنا ہوتا ہے، عام طور پر گراف کے عمودی حصوں کی تعداد کے فنکشن کے طور پر۔ ان مسائل کو یا تو بالکل (الجبرائی گنتی کے مسئلے کے طور پر) یا غیر علامتی طور پر حل کیا جا سکتا ہے۔ ریاضی کے اس شعبے کے علمبردار جارج پولیا، آرتھر کیلی اور جے ہاورڈ ریڈ فیلڈ تھے۔ لیبلڈ بمقابلہ غیر لیبلڈ مسائل کچھ گرافیکل گنتی کے مسائل میں، گراف کے عمودی حصوں کو اس طرح سے لیبل کیا جاتا ہے کہ وہ ایک دوسرے سے ممتاز ہوں، جبکہ دیگر مسائل میں عمودی حصوں کی کسی بھی ترتیب کو ایک ہی گراف بنانے کے لیے سمجھا جاتا ہے، اس لیے عمودی حصوں کو یکساں یا غیر لیبلڈ سمجھا جاتا ہے۔ عام طور پر، لیبل والے مسائل آسان ہوتے ہیں۔ جیسا کہ زیادہ عام طور پر مشترکہ گنتی کے ساتھ، پولیا گنتی تھیوریم غیر لیبل شدہ مسائل کو لیبل والے مسائل تک کم کرنے کا ایک اہم ذریعہ ہے: ہر غیر لیبل شدہ کلاس کو لیبل شدہ اشیاء کی ہم آہنگی کلاس کے طور پر سمجھا جاتا ہے۔ درست گنتی کے فارمولے اس شعبے کے کچھ اہم نتائج میں درج ذیل شامل ہیں۔ لیبل والے این-ورٹیکس سادہ غیر ہدایت شدہ گرافوں کی تعداد 2n (n & hairsp; −1)/2 ہے۔ لیبل والے این-ورٹیکس سادہ ڈائریکٹڈ گرافوں کی تعداد 2n (این & ہیئر ایس پی ؛ −1) ہے۔ جڑے ہوئے لیبل والے این-ورٹیکس غیر ہدایت شدہ گرافوں کا نمبر سی این اس تکرار کے تعلق کو مطمئن کرتا ہے جس سے کوئی آسانی سے حساب لگا سکتا ہے، n = 1، 2، 3 کے لیے، کہ سی این کے لیے اقدار 1، 1، 4، 38، 728، 26704، 1866-256، ہیں۔ لیبل والے n-ورٹیکس سے پاک درختوں کی تعداد nn−2 (کیلی کا فارمولا) ہے۔ غیر لیبل شدہ این-ورٹیکس کیٹرپلرز کی تعداد گراف ڈیٹا بیس ہے مختلف تحقیقی گروپوں نے قابل تلاش ڈیٹا بیس فراہم کیا ہے جو چھوٹے سائز کی مخصوص خصوصیات کے ساتھ گراف کی فہرست بناتا ہے۔ مثال کے طور پر ہاؤس آف گرافز سمال گراف ڈیٹا بیس حوالہ جات عددی امتزاج