Формула Келі (теорія графів)

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Усі дерева з 2,3,4 поміченими вершинами

В теорії графів формула Келі обчислює кількість неорієнтованих дерев з n поміченими вершинами. Згідно з даною формулою кількість таких дерев рівна

n^{n-2}.\,.

Формула названа на честь відомого англійського математика Артура Келі, який вивів її у 1889 році.

Доведення[ред.ред. код]

Існує кілька доведень даного твердження. Подане нижче належить американському математику Джеймсу Пітману.

Для доведення формули ми двома різними способами обчислимо кількість послідовностей орієнтованих ребер, якими можна доповнити пустий граф з n поміченими вершинами до кореневого дерева з n поміченими вершинами. Перший спосіб полягає в наступному: обирається будь яке неорієнтоване дерево з n поміченими вершинами. Позначимо їх кількість Tn(саме це число нам треба обчислити). Далі з n вершин обираємо один корінь. Після цього однозначно визначається орієнтація всіх ребер дерева і залишається лиш вибрати певну послідовність з цих n-1 ребер. Тож остаточно необхідна кількість рівна

T_nn(n - 1)! = T_nn!.

Інший спосіб полягає в покроковому додаванні орієнтованих ребер і обчисленні кількості варіантів на кожному кроці. Після nk кроків отримується ліс з k кореневих дерев. Початковою вершиною наступного ребра може бути будь-яка з n вершин, а кінцевою котрась з коеневих вершин за винятком кореневої вершини дерева до якого належить початкова вершина. Отже загальна кількість можливих способів рівна n(k − 1). Щоб отримати необхідну кількість слід перемножити кількість варіантів на кожному з n-1 кроків:

\prod_{k=2}^{n} n(k-1) = n^{n-1} (n-1)! = n^{n-2} n!.

Очевидно оба одержані результати повинні бути рівними, тож ми отримуємо тотожність:

\displaystyle T_n n!=n^{n-2}n!

і як наслідок:

\displaystyle T_n =n^{n-2},

що й слід було довести.

Для термінології дивіться:

Література[ред.ред. код]

  • Р. Уилсон (1977). Введение в теорию графов. Москва: Мир. 
  • M. Aigner, G. Ziegler (1998). Proofs from the book. Springer Verlag.