Перечисление графов

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

В комбинаторике , области математики , перечисление графов описывает класс задач комбинаторного перечисления , в которых необходимо подсчитать неориентированные или ориентированные графы определенных типов, как правило, как функцию от числа вершин графа. ^[1] Эти задачи могут быть решены либо точно (как задача алгебраического перечисления ), либо асимптотически . Пионерами в этой области математики были Джордж Полиа , ^[2] Артур Кейли ^[3] и Дж. Говард Редфилд . ^[4]

Маркированные и немаркированные проблемы

В некоторых графических задачах перечисления вершины графа считаются помеченными таким образом, чтобы их можно было отличить друг от друга, в то время как в других задачах любая перестановка вершин считается образующей тот же граф, поэтому вершины считаются идентичными или непомеченными . В целом, помеченные задачи, как правило, проще. ^[5] Как и в случае с комбинаторным перечислением в более общем смысле, теорема о перечислении Полиа является важным инструментом для сведения непомеченных задач к помеченным: каждый непомеченный класс рассматривается как класс симметрии помеченных объектов.

Число непомеченных графов с вершинами до сих пор неизвестно в решении в замкнутой форме , ^[6] но поскольку почти все графы асимметричны , это число является асимптотическим к ^[7] ${\displaystyle n}$ $${\displaystyle {\frac {2^{\tbinom {n}{2}}}{n!}}.}$$

Точные формулы перечисления

Некоторые важные результаты в этой области включают следующее.

• Число помеченных n- вершинных простых неориентированных графов равно 2 ^{n ( n  −1)/2} . ^[8]
• Число помеченных n -вершинных простых ориентированных графов равно 2 ^{n ( n  −1)} . ^[9]
• Число C _n связных помеченных n -вершинных неориентированных графов удовлетворяет рекуррентному соотношению ^[10]

${\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, ...(последовательность A001187 в OEIS )

• Число помеченных деревьев, свободных от n вершин , равно n ^{n −2} ( формула Кэли ).
• Число немаркированных n -вершинных гусениц равно ^[11]

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

Графическая база данных

Различные исследовательские группы предоставили поисковую базу данных, которая содержит список графов с определенными свойствами небольших размеров. Например

• Дом графиков
• База данных малых графов

Ссылки

1. Харари, Фрэнк ; Палмер, Эдгар М. (1973). Графическое перечисление . Academic Press . ISBN 0-12-324245-2.
2. Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Акта Математика. 68 (1937), 145-254
3. "Кейли, Артур (CLY838A)". База данных выпускников Кембриджа . Кембриджский университет.
4. Теория групповых редуцированных распределений. American J. Math. 49 (1927), 433-455.
5. Харари и Палмер, стр. 1.
6. Слоан, Н. Дж. А. (ред.). «Последовательность A000088 (Число графов на n непомеченных узлах)». Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
7. Кэмерон, Питер Дж. (2004), «Автоморфизмы графов», в Бейнеке, Лоуэлл У.; Уилсон, Робин Дж. (ред.), Топики алгебраической теории графов , Энциклопедия математики и ее приложений, т. 102, Cambridge University Press, стр. 137–155, ISBN 0-521-80197-4
8. Харари и Палмер, стр. 3.
9. Харари и Палмер, стр. 5.
10. Харари и Палмер, стр. 7.
11. Харари, Фрэнк ; Швенк, Аллен Дж. (1973), «Число гусениц» (PDF) , Дискретная математика , 6 (4): 359–365, doi :10.1016/0012-365x(73)90067-8, hdl : 2027.42/33977.