تعداد الرسم البياني

في علم التوافيق ، وهو فرع من فروع الرياضيات ، يُشير مصطلح تعداد الرسوم البيانية إلى فئة من مسائل التعداد التوافقي التي تتطلب عدّ الرسوم البيانية غير الموجهة أو الموجهة من أنواع معينة، عادةً كدالة لعدد رؤوس الرسم البياني. ^{[ 1 ]} يمكن حل هذه المسائل إما بدقة (كمسألة تعداد جبري ) أو تقاربياً . ومن رواد هذا المجال من الرياضيات جورج بوليا ، ^{[ 2 ]} وآرثر كايلي ^{، [ 3 ]} وج . هوارد ريدفيلد . ^{[ 4 ]}

في بعض مسائل التعداد البياني، تُعتبر رؤوس الرسم البياني مُصنّفة بطريقة تُمكّن من تمييزها عن بعضها، بينما في مسائل أخرى، يُعتبر أي تبديل للرؤوس مُكوّنًا للرسم البياني نفسه، وبالتالي تُعتبر الرؤوس متطابقة أو غير مُصنّفة . وبشكل عام، تميل المسائل المُصنّفة إلى أن تكون أسهل. ^{[ 5 ]} وكما هو الحال مع التعداد التوافقي بشكل عام، تُعدّ نظرية بوليا للتعداد أداةً مهمةً لتحويل المسائل غير المُصنّفة إلى مسائل مُصنّفة: حيث تُعتبر كل فئة غير مُصنّفة فئة تناظر للعناصر المُصنّفة.

عدد الرسوم البيانية غير المصنفة التي تحتوي على${\displaystyle n}$لا يزال عدد الرؤوس غير معروف في حل مغلق الشكل ، ^{[ 6 ]} ولكن نظرًا لأن جميع الرسوم البيانية تقريبًا غير متماثلة، فإن هذا العدد يقترب من ^{[ 7 ].}$${\displaystyle {\frac {2^{\tbinom {n}{2}}}{n!}}.}$$

تتضمن بعض النتائج المهمة في هذا المجال ما يلي.

• عدد الرسوم البيانية البسيطة غير الموجهة ذات n رأسًا والمصنفة هو 2 ^{n ( n −1)/2} . ^{[ 8 ]}
• عدد الرسوم البيانية الموجهة البسيطة ذات الرؤوس n المصنفة هو 2 ^{n ( n −1)} . ^{[ 9 ]}
• عدد C _n من الرسوم البيانية غير الموجهة ذات n رأس والمتصلة والمصنفة يحقق علاقة التكرار ^{[ 10 ]}

${\displaystyle 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}.}$

ومنها يمكن حساب قيم C _n بسهولة، وذلك لـ n = 1، 2، 3، ...

1، 1، 4، 38، 728، 26704، 1866256، ... (التسلسل A001187 في OEIS )

• عدد الأشجار الخالية من الرؤوس المصنفة n هو n ^{n −2} ( صيغة كايلي ).
• عدد اليرقات غير المصنفة ذات الرؤوس n هو ^{[ 11 ]}

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

قدمت مجموعات بحثية مختلفة قواعد بيانات قابلة للبحث تضم قوائم بالرسوم البيانية ذات خصائص معينة، مثل صغر حجمها. على سبيل المثال

• بيت الرسوم البيانية
• قاعدة بيانات الرسوم البيانية الصغيرة