پرش به محتویات

شمارش گراف‌های برچسب‌دار

گراف‌های برچسب‌دار

فرض کنید تعداد رئوس در یک گراف $n$ باشد. باید تعداد $G_n$ گراف‌های برچسب‌دار با $n$ رأس را محاسبه کنیم (برچسب‌دار به این معنی است که رئوس با اعداد ۱ تا $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$ رأس قرار دارد برابر است با $k \binom{n}{k} C_k G_{n-k}$ (به $\binom{n}{k}$ طریق می‌توان $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]$$