Перерахування графів — категорія завдань нумераційної комбінаторики, в яких потрібно перерахувати неорієнтовані або орієнтовані графи певних типів, як правило, у вигляді функції від числа вершин графу. Ці завдання можуть бути розв'язані або точно (як завдання ) або асимптотично.
Піонерами в цій галузі математики були Пойа, КеліArthur Cayley A Cambridge Alumni Database. University of Cambridge. і Редфілд.
Позначені і непозначені задачі У деяких задачах перерахування графів вершини графів вважаються позначеними, тобто відрізняються одна від одної. В інших задачах будь-яка перестановка вершин вважається тим самим графом, так що вершини вважаються ідентичними або непозначеними. У загальному випадку, позначені задачі, як правило, виявляються простішими. Теорема Редфілда — Пойї є важливим засобом для зведення непозначеної задачі до позначеної — кожен непозначений клас вважається класом симетрії позначених об'єктів.
Точні формули перерахування Деякі важливі результати в цій галузі.
Кількість позначених простих неорієнтованих графів з n вершинами дорівнює 2n(n − 1)/2 Кількість позначених простих орієнтованих графів з n вершинами дорівнює 2n(n − 1) Число Cn зв'язних позначених неорієнтованих графів з n вершинами задовольняє рекурентному співвідношенню
з якого можна легко обчислити для n = 1, 2, 3, ..., що значення Cn дорівнюють: 1, 1, 4, 38, 728, 26704, 1866256, ...
Кількість позначених вільних дерев з n вершинами дорівнює nn − 2 (формула Келі). Число непозначених гусениць з n вершинами дорівнює
Примітки
Література