Открыть главное меню
Полный список всех деревьев с 2,3 и 4 помеченными вершинами: дерево с 2 вершинами, дерева с 3 вершинами и деревьев с 4 вершинами.

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

Помеченные и непомеченные задачиПравить

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

Точные формулы перечисленияПравить

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

  • Число помеченных простых неориентированных графов с n вершинами равно 2n(n − 1)/2[5]
  • Число помеченных простых ориентированных графов с n вершинами равно 2n(n − 1)[6]
  • Число Cn связных помеченных неориентированных графов с n вершинами удовлетворяет рекуррентному соотношению[7]
 
из которого можно легко вычислить для n = 1, 2, 3, …, что значения Cn равны[8]:
1, 1, 4, 38, 728, 26704, 1866256, …
 

ПримечанияПравить

  1. 1 2 Harary, Palmer, 1973.
  2. Pólya, 1937, с. 145—254.
  3. Arthur Cayley (недоступная ссылка) 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.

ЛитератураПравить