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

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

В комбинаторике , области математики , перечисление графов описывает класс комбинаторных задач перечисления , в которых необходимо подсчитывать неориентированные или ориентированные графы определенных типов, обычно в зависимости от количества вершин графа. Эти задачи можно решать либо точно (как задача алгебраического перечисления ), либо асимптотически .Пионерами в этой области математики были Джордж Пойа , Артур Кэли и Дж. Ховард Редфилд .

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

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

Формулы точного перечисления

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

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

$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. ^{п -2} ( формула Кэли ).
• Число немеченых n -вертексных гусениц равно

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

База данных графов

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

• Дом графов
• Малая графовая база данных