Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/nir/uir/gorbunov.doc Дата изменения: Wed Jul 1 17:31:02 2009 Дата индексирования: Tue Oct 2 04:20:44 2012 Кодировка: koi8-r Поисковые слова: единицы измерений

Дима Горбунов (школа «Интеллектуал», 7 класс).
"Подсчет числа пронумерованных деревьев"

Задача
Какое количество деревьев можно построить на n пронумерованных вершинах?

Очевидно, что на 1 вершине можно построить лишь 1 дерево с 0 ребрами. На 2
вершинах - 1 дерево. На 3 вершинах - 3 дерева. На 4 - 16. Ниже показаны
способы для таких количеств вершин.
[pic]
Пусть n=5. Теперь прямой подсчет уже достаточно сложен. Подсчитаем кол-во
неизоморфных деревьев, их три:
[pic]
Первое из них можно пронумеровать 5 способами, второе - [pic]=60, третье -
тоже [pic]=60. Сложим все это - 5 + 60 + 60 = 125. Соберем данные в
таблицу:
|Кол-во вершин |Кол-во деревьев |
|1 |1 |
|2 |1 |
|3 |3 |
|4 |16 |
|5 |25 |

Выдвигаем теорему 1.
Теорема 1. Количество деревьев, которые можно построить на n вершинах,
равно nn-2.
Теперь докажем эту теорему.
Перед этим введем новые понятия.
Определения. Помеченным деревом называется дерево, в котором выделены две
вершины, одну будем называть левым концом, а другую - правым. Левый конец
будем далее отмечать кружочком, правый - квадратом. Пример помеченного
дерева на 3 вершинах:


1 2 3
Пусть Fn - количество помеченных деревьев на n вершинах, а Kn- количество
деревьев на n вершинах графа.
Для доказательства потребуется лемма.
Лемма 1. Fn = Knn2.
Действительно, берем количество деревьев и выбираем одну из вершин n
способами и другую - n способами. Итого - Knn2=Fn , ч.т.д.
Доказательство теоремы 1.
По лемме 1 Fn = Knn2. Если мы докажем, что Fn=nn, то Kn=Fn\n2=nn\n2=nn-2.
Рассмотрим множество помеченных деревьев на n вершинах и множество
ориентированных графов, у которых:
1) Из каждой вершины идет ровно одно ребро;

2) Между двумя вершинами не более двух ребер;

3) Разрешены петли.

Количество способов построить такой ориентированный граф - nn , поскольку
из первой вершины ребро можно провести n способами (петля и n-1 вершина),
из второго - тоже n и т.д, в результате получается nn.
Докажем, что эти множества равномощны. Рассмотрим какой-либо
ориентированный граф и попробуем превратить его в помеченное дерево. Введем
новое множество M1, туда включим все вершины циклов графа, причем номера
вершин идут в порядке возрастания. Введем функцию f(x) - вершину, в которую
идет ребро из вершины x. Пусть M1 = {a, b, c, d, ., z}. Тогда пусть M2 =
{f(a), f(b), f(c), ., f(z)}. Соединим все вершины множества M2 ребрами - из
f(a) в f(b), из f(b) в f(c) и т.д. При этом отметим f(a) левым концом, а
f(z) - правым. Все остальные вершины (не включенные в множество М2) -
соединим точно так же, как и в ориентированном графе. Получилось помеченное
дерево, т.к. мы убрали все циклы.
Нетрудно получить и обратный результат - из дерева сделать ориентированный
граф. Возьмем P - путь из левого конца в правый и включим его без изменений
в множество M2. Расположим числа в множестве P в порядке возрастания и
включим результат в множество M1. M1 = {a, b, c, d, ., z}. M2 = {f(a),
f(b), f(c), ., f(z)}. Строим циклы ориентированного графа по этим двум
множествам. Оставшиеся вершины подключаем так же, как они подключены к
вершинам циклов, по направлению к ним. Получился ориентированный граф.
Получается взаимно однозначное соответствие, т.к. из каждого помеченного
дерева получается ориентированный граф, а из него получается то же самое
помеченное дерево. Из двух ориентированных графов не может получиться одно
и то же дерево, т.к. тогда это дерево дает 2 ориентированных графа, а этого
быть не может. Аналогично и с деревьями - из двух помеченных деревьев не
может получиться один ориентированный граф, т.к. из него тогда получается
два дерева. Противоречие. Значит, установлено взаимно однозначное
соответствие, а значит, эти множества равномощны. Теорема доказана.


Комментарий руководителя.
Дима довольно быстро угадал общую формулу из рассмотрения частных случаев,
а потом долго не мог её доказать. В конце концов я стал наводить его на
идею доказательства, которое знал сам, но не успел этого сделать, как Дима
принёс своё красивое доказательство.
Проф. С.К. Ландо написал мне, что доказательство правильное, но затруднился
«с ходу» оценить степень его новизны.

Сгибнев А.И.