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

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

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

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

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

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

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

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

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

${\displaystyle C_{n}=2^{n \choose 2}-{\frac {1}{n}}\sum _{k=1}^{n-1}k{n \choose k}2^{n-k \choose 2}C_{k}.}$

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

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

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

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

Примітки

1. Harary, Palmer, 1973.
2. Pólya, 1937, с. 145—254.
3. Arthur Cayley^{[недоступне посилання з червня 2019]} A Cambridge Alumni Database. University of Cambridge.
4. Redfield, 1927, с. 433—455.
5. Harary, Palmer, 1973, с. 3.
6. Harary, Palmer, 1973, с. 5.
7. Harary, Palmer, 1973, с. 7.
8. послідовність A001187 з Онлайн енциклопедії послідовностей цілих чисел, OEIS
9. Harary, Schwenk, 1973, с. 359–365.

Література

• , Palmer E. M. Graphical Enumeration. — , 1973. — .
• , Schwenk A. J. The number of caterpillars // Discrete Mathematics. — 1973. — Т. 6, вип. 4. — С. 359–365. — DOI:10.1016/0012-365x(73)90067-8.
• Pólya G. Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen // . — 1937. — Т. 68, вип. 1. — DOI:10.1007/BF02546665.
• Redfield J. H. The theory of group-reduced distributions // American J. Math. — 1927. — Т. 49.