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

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

Повний список всіх дерев з 2,3 і 4 позначеними вершинами:
*

2^{2-2}=1

дерево з 2 вершинами;
*

3^{3-2}=3

дерева з 3 вершинами;
*

4^{4-2}=16

дерев з 4 вершинами.

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

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

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

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

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

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

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 дорівнюють[8]:

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

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

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

Примітки

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

Література

Harary F., Palmer E. M. Graphical Enumeration. — Academic Press, 1973. — ISBN 0-12-324245-2.
Harary F., 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 // Acta Mathematica. — 1937. — Т. 68, вип. 1. — DOI:10.1007/BF02546665.
Redfield J. H. The theory of group-reduced distributions // American J. Math. — 1927. — Т. 49.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[FOOTNOTEHarary,_Palmer1973-1] Harary, Palmer, 1973.

[FOOTNOTEPólya1937145—254-2] Pólya, 1937, с. 145—254.

[3] Arthur Cayley^{[недоступне посилання з червня 2019]} A Cambridge Alumni Database. University of Cambridge.

[FOOTNOTERedfield1927433—455-4] Redfield, 1927, с. 433—455.

[FOOTNOTEHarary,_Palmer19733-5] Harary, Palmer, 1973, с. 3.

[FOOTNOTEHarary,_Palmer19735-6] Harary, Palmer, 1973, с. 5.

[FOOTNOTEHarary,_Palmer19737-7] Harary, Palmer, 1973, с. 7.

[8] послідовність A001187 з Онлайн енциклопедії послідовностей цілих чисел, OEIS

[FOOTNOTEHarary,_Schwenk1973359–365-9] Harary, Schwenk, 1973, с. 359–365.