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

Полный список всех свободных деревьев на 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] Как и в случае с комбинаторным перечислением в более общем смысле, теорема о перечислении Полиа является важным инструментом для сведения немеченых проблем к помеченным: каждый немаркированный класс рассматривается как класс симметрии помеченных объектов.

Формулы точного перечисления [ править ]

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

• Количество помеченных n -вершинных простых неориентированных графов равно 2 ^{n ( n  - 1) / 2} . ^[6]
• Количество помеченных n -вершинных простых ориентированных графов равно 2 ^{n ( n  - 1)} . ^[7]
• Число С _п о подключен меченного п -vertex неориентированных графов удовлетворяет рекуррентное соотношение ^[8]

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

из которого легко вычислить для n = 1, 2, 3, ..., что значения для C _n равны

1, 1, 4, 38, 728, 26704, 1866256, ... (последовательность A001187 в OEIS )

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

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

База данных графиков [ править ]

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

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

Ссылки [ править ]