Підрахунок позначених графів

Позначені графи

Нехай кількість вершин у графі дорівнює $n$. Нам потрібно обчислити кількість $G_n$ позначених графів з $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$ вершинами (є $\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]$$

Відеоматеріали