Відкрити головне меню
Повний список всіх дерев з 2,3 і 4 позначеними вершинами:
* дерево з 2 вершинами;
* дерева з 3 вершинами;
* дерев з 4 вершинами.

Перерахування графів — категорія завдань нумераційної комбінаторики, в яких потрібно перерахувати неорієнтовані або орієнтовані графи певних типів, як правило, у вигляді функції від числа вершин графа[1]. Ці завдання можуть бути розв'язані або точно (як завдання алгебричного перерахування[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. а б Harary, Palmer, 1973
  2. Pólya, 1937, с. 145—254
  3. Arthur Cayley[недоступне посилання з червень 2019] 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

ЛітератураРедагувати