Перерахування графів

Повний список всіх дерев з 2,3 і 4 позначеними вершинами:
* $2^{2-2}=1$ дерево з 2 вершинами;
* $3^{3-2}=3$ дерева з 3 вершинами;
* $4^{4-2}=16$ дерев з 4 вершинами.

Перерахування графів — категорія завдань нумераційної комбінаторики, в яких потрібно перерахувати неорієнтовані або орієнтовані графи певних типів, як правило, у вигляді функції від числа вершин графуШаблон:Sfn. Ці завдання можуть бути розв'язані або точно (як завдання Шаблон:Нп) або асимптотично.

Піонерами в цій галузі математики були ПойаШаблон:Sfn, Келі і РедфілдШаблон:Sfn.

Позначені і непозначені задачі

У деяких задачах перерахування графів вершини графів вважаються позначеними, тобто відрізняються одна від одної. В інших задачах будь-яка перестановка вершин вважається тим самим графом, так що вершини вважаються ідентичними або непозначеними. У загальному випадку, позначені задачі, як правило, виявляються простішимиШаблон:Sfn. Теорема Редфілда — Пойї є важливим засобом для зведення непозначеної задачі до позначеної — кожен непозначений клас вважається класом симетрії позначених об'єктів.

Точні формули перерахування

Деякі важливі результати в цій галузі.

• Кількість позначених простих неорієнтованих графів з n вершинами дорівнює 2^{n(n − 1)/2}Шаблон:Sfn
• Кількість позначених простих орієнтованих графів з n вершинами дорівнює 2^{n(n − 1)}Шаблон:Sfn
• Число C_n зв'язних позначених неорієнтованих графів з n вершинами задовольняє рекурентному співвідношеннюШаблон:Sfn

$C_n=2^{(\genfrac{}{}{0ex}{}{n}{2})}-\frac{1}{n}\sum _{k=1}^{n-1}k(\genfrac{}{}{0ex}{}{n}{k})2^{(\genfrac{}{}{0ex}{}{n-k}{2})}{C}_k.$

з якого можна легко обчислити для n = 1, 2, 3, ..., що значення C_n дорівнюють:

1, 1, 4, 38, 728, 26704, 1866256, ...

• Кількість позначених вільних дерев з n вершинами дорівнює n^{n − 2} (формула Келі).
• Число непозначених гусениць з n вершинами дорівнюєШаблон:Sfn

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

Література

• Шаблон:Книга-ру
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття