লেবেলড গ্রাফ গণনা#
লেবেলড গ্রাফ#
ধরা যাক একটি গ্রাফে ভার্টেক্সের সংখ্যা $n$। আমাদের $n$টি ভার্টেক্স বিশিষ্ট লেবেলড গ্রাফের সংখ্যা $G_n$ গণনা করতে হবে (লেবেলড মানে ভার্টেক্সগুলো $1$ থেকে $n$ পর্যন্ত সংখ্যা দ্বারা চিহ্নিত)। গ্রাফের এজগুলো অনির্দেশিত বিবেচনা করা হয়, এবং লুপ ও মাল্টিপল এজ নিষিদ্ধ।
আমরা গ্রাফের সব সম্ভাব্য এজের সেট বিবেচনা করি। প্রতিটি এজ $(i, j)$-এর জন্য আমরা ধরে নিতে পারি যে $i < j$ (কারণ গ্রাফটি অনির্দেশিত এবং কোনো লুপ নেই)। তাই সব এজের সেটের কার্ডিনালিটি $\binom{n}{2}$, অর্থাৎ $\frac{n(n-1)}{2}$।
যেহেতু যেকোনো লেবেলড গ্রাফ তার এজ দ্বারা অনন্যভাবে নির্ধারিত, তাই $n$টি ভার্টেক্স বিশিষ্ট লেবেলড গ্রাফের সংখ্যা:
$$G_n = 2^{\frac{n(n-1)}{2}}$$সংযুক্ত লেবেলড গ্রাফ#
এখানে আমরা অতিরিক্ত শর্ত আরোপ করি যে গ্রাফটি সংযুক্ত হতে হবে।
$n$টি ভার্টেক্স বিশিষ্ট সংযুক্ত গ্রাফের প্রয়োজনীয় সংখ্যাকে $C_n$ দ্বারা চিহ্নিত করি।
প্রথমে আমরা আলোচনা করব কতগুলো বিচ্ছিন্ন গ্রাফ আছে। তারপর সংযুক্ত গ্রাফের সংখ্যা হবে $G_n$ থেকে বিচ্ছিন্ন গ্রাফের সংখ্যা বাদ দিলে। আরও বিশেষভাবে, আমরা বিচ্ছিন্ন, রুটেড গ্রাফ-এর সংখ্যা গুনব। রুটেড গ্রাফ হলো একটি গ্রাফ যেখানে আমরা একটি ভার্টেক্সকে রুট হিসেবে লেবেল করে বিশেষভাবে চিহ্নিত করি। স্পষ্টতই $n$টি লেবেলড ভার্টেক্স বিশিষ্ট একটি গ্রাফকে রুট করার $n$টি সম্ভাবনা আছে, তাই বিচ্ছিন্ন গ্রাফের সংখ্যা পেতে শেষে আমাদের বিচ্ছিন্ন রুটেড গ্রাফের সংখ্যাকে $n$ দ্বারা ভাগ করতে হবে।
রুট ভার্টেক্সটি $1, \dots n-1$ আকারের একটি সংযুক্ত কম্পোনেন্টে থাকবে। এমন গ্রাফের সংখ্যা $k \binom{n}{k} C_k G_{n-k}$ যেখানে রুট ভার্টেক্স $k$টি ভার্টেক্স বিশিষ্ট একটি সংযুক্ত কম্পোনেন্টে থাকে (কম্পোনেন্টের জন্য $k$টি ভার্টেক্স বাছাই করার $\binom{n}{k}$ উপায় আছে, এগুলো $C_k$ উপায়ে সংযুক্ত হয়, রুট ভার্টেক্স $k$টি ভার্টেক্সের যেকোনো একটি হতে পারে, এবং বাকি $n-k$টি ভার্টেক্স যেকোনোভাবে সংযুক্ত/বিচ্ছিন্ন হতে পারে, যা $G_{n-k}$ ফ্যাক্টর দেয়)। তাই $n$টি ভার্টেক্স বিশিষ্ট বিচ্ছিন্ন গ্রাফের সংখ্যা:
$$\frac{1}{n} \sum_{k=1}^{n-1} k \binom{n}{k} C_k G_{n-k}$$এবং অবশেষে সংযুক্ত গ্রাফের সংখ্যা:
$$C_n = G_n - \frac{1}{n} \sum_{k=1}^{n-1} k \binom{n}{k} C_k G_{n-k}$$$k$টি সংযুক্ত কম্পোনেন্ট বিশিষ্ট লেবেলড গ্রাফ#
আগের সেকশনের সূত্রের ভিত্তিতে, আমরা শিখব কীভাবে $n$টি ভার্টেক্স এবং $k$টি সংযুক্ত কম্পোনেন্ট বিশিষ্ট লেবেলড গ্রাফের সংখ্যা গণনা করতে হয়।
এই সংখ্যাটি ডায়নামিক প্রোগ্রামিং ব্যবহার করে গণনা করা যায়। আমরা $D[i][j]$ গণনা করব — $i$টি ভার্টেক্স এবং $j$টি কম্পোনেন্ট বিশিষ্ট লেবেলড গ্রাফের সংখ্যা — প্রতিটি $i \le n$ এবং $j \le k$-এর জন্য।
আসুন আলোচনা করি কীভাবে পরবর্তী উপাদান $D[n][k]$ গণনা করা যায় যদি আমরা আগের মানগুলো জানি। আমরা একটি সাধারণ পদ্ধতি ব্যবহার করি — শেষ ভার্টেক্সটি (ইনডেক্স $n$) নিই। এই ভার্টেক্সটি কোনো একটি কম্পোনেন্টে থাকে। যদি এই কম্পোনেন্টের আকার $s$ হয়, তাহলে এমন ভার্টেক্সের সেট বাছাই করার $\binom{n-1}{s-1}$ উপায় আছে, এবং সেগুলো সংযুক্ত করার $C_s$ উপায় আছে। গ্রাফ থেকে এই কম্পোনেন্ট সরিয়ে নিলে বাকি থাকে $n-s$টি ভার্টেক্স এবং $k-1$টি সংযুক্ত কম্পোনেন্ট। অতএব আমরা নিম্নলিখিত রিকারেন্স সম্পর্ক পাই:
$$D[n][k] = \sum_{s=1}^{n} \binom{n-1}{s-1} C_s D[n-s][k-1]$$