Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-02-26

1 Самый простой способ посчитать что-либо - это соотнести объекты с чем-то более простым. Например, можно изучить абстрактные операции на бытовых примерах: соотносить числа и множества с книгами и книжными полками.

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

3 <h2>Теорема Кейли</h2>

4 Теорема Кейли применяется, чтобы подсчитать количество меченых прямых деревьев. Другими словами, теорема Кейли помогает ответить на вопрос: "Сколько всего существует деревьев на фиксированном множестве вершин множестве V?".

5 При этом характер элементов V не важен. Например, мы можем взять такое выражение:

6 V = [n] В этом случае ответ будет зависеть не от [n], а только от размера V. Обозначим это число через t(n).

7 Теперь сгенерируем деревья. Сначала определяем все возможные формы деревьев - то есть немеченые деревья на n вершинах.

8 Затем найдем все способы присвоить элементам V их метки:

9 В правой части этой схемы мы видим числа 1, 1, 3, 16 и 125. Они равны n^(n-2).

10 Таким образом можно сформулировать теорему Кейли:

11 Для всех n верно, что число прямых деревьев на множестве вершин размера n равно n^(n-2)

12 Попробуем доказать эту теорему с помощью биекции.

13 <h3>Доказательство с помощью биекции</h3>

14 Код Прюфера - это такой способ кодирования деревьев с n вершинами с помощью последовательности.

15 Чтобы доказать эту теорему, выполним первый шаг:

16 Создадим код Прюфера ( y1 , . . . . , yn - 1 ) дерева T на множестве вершин V = [n]

17 Для этого нам нужно рекурсивно определить три последовательности:

18 <ul><li>(x1 , . . . . , xn - 1 )</li>

19 <li>( y1 , . . . . , yn - 1 ) вершин</li>

20 <li>(T1 , . . . . , Tn - 1 ) деревьев</li>

21 </ul>Эти последовательности можно определить следующим образом:

22 <ul><li>T1 := T</li>

23 <li>Для 1 ≤ i ≤ n - 1, пусть xi - вершина степени -1 в Ti с наименьшим индексом</li>

24 <li>Для 1 ≤ i ≤ n - 1, пусть yi - сосед xi в Ti</li>

25 <li>Для 1 ≤ i ≤ n-2, пусть Ti + 1 := Ti - xi - дерево, которое получили, когда удалили вершины xi и ребра {xi , yi }</li>

26 </ul>Рассмотрим следующее дерево:

27 У нас есть две последовательности:

28 <ul><li>(x1 , . . . . , x9 ) = (3, 4, 2, 5, 6, 7, 1, 8, 9)</li>

29 <li>( y1 , . . . . , y9 ) = (2, 2, 1, 1, 7, 1, 10, 10, 10)</li>

30 </ul>Рассмотрим код Прюфера ( y1 , . . . . , yn - 1 ).

31 У каждого дерева есть хотя бы две вершины степени 1, поэтому вершина n никогда не будет удалена. Следовательно, yn - 1 = n.

32 Выберем k in {1, . . . , n - 2}. Удаляются только вершины степени -1, поэтому степень вершины v в дереве Tk на единицу больше, чем число вхождений v среди ( yk , . . . . , yn-2 ).

33 Получается, вершины степени 1 в Tk - это те вершины, которые не встречаются в этом выражении:

34 {x1 , . . . . , xk-1 } cup { yk , . . . . , yn-2 }

35 Теперь xk - наименьший элемент из [n], который не входит в множество. Такой элемент всегда существует, и у него не более n - 2 членов.

36 Отсюда следует, что из последовательности ( y1 , . . . . , yn-2 ) можно восстановить:

37 <ul><li>(y1 , . . . . , yn - 1 )</li>

38 <li>(x1 , . . . . , xn - 1 )</li>

39 </ul>Поэтому мы можем восстановить в таком порядке: Tn - 1 , . . . , T1 = T.

40 Каждое дерево дает последовательность, с помощью которой можно восстановить уникальное дерево. В этом случае повторное присоединение xk к yk однозначно определено. Поэтому количество последовательностей (y1, . . . ,yn-2) и количество деревьев должны быть равны. Число последовательностей равно n^n-2, так как каждый yi принимает n различных значений.

41 Биекция - это не единственный способ доказательства теоремы Кейли. Еще естьумная конструкция, которая помогает в подсчетах более сложных структур. Этот прием встречается все чаще, но пока мы не будем останавливаться на нем подробно из-за объемного и трудоемкого доказательства.

42 <h2>Выводы</h2>

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

44 Чтобы разобраться в этом теореме, мы познакомились с такими фундаментальными понятиями, как биекция и код Прюфера. Эти термины будут полезны далее в курсе по комбинаторике и в других курсах по дискретной математике.