Теорема Кэли о числе деревьев

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Полный список деревьев на 2, 3 и 4 пронумерованных вершинах: 2^{2-2}=1 дерево с 2 вершинами, 3^{3-2}=3 дерева с 3 вершинами и 4^{4-2}=16 деревьев с 4 вершинами.

Теорема Кэли о числе деревьев — названное в честь А. Кэли явное выражение в теории графов для числа деревьев с данным числом пронумерованных вершин. А именно, оказывается, что на n вершинах, пронумерованных числами от 1 до n, существует ровно n^{n-2} различных деревьев.

Количество деревьев на n пронумерованных вершинах оказывается также равным числу разложений n-цикла (12…n) в произведение (n-1) транспозиции, а также числу (соответствующим образом нормированных) многочленов степени n с заданными (n-1) критическими значениями общего положения. Наконец, это последнее является частным случаем топологической классификации разветвлённых накрытий сферы Римана — тем самым, подсчёт числа деревьев оказывается частным случаем вычисления чисел Гурвица, соответствующим случаю накрывающей поверхности рода 0.

Код Прюфера[править | править вики-текст]

Код Прюфера — это способ однозначного кодирования n-вершинного помеченного дерева упорядоченной последовательностью из n-2 номеров его вершин. Из теоремы Кэли следует, что каждой такой последовательности можно сопоставить некоторое дерево, и наоборот, то есть между ними существует взаимооднозначное соответствие.

Составление кода Прюфера по дереву[править | править вики-текст]

В ходе составления кода Прюфера из дерева поочерёдно удаляются вершины, пока их не останется только две.

Без ограничения общности предполагается, что вершины помечены целыми числами. Первым элементом кода Прюфера будет номер вершины, смежной с минимальным по номеру листом. После добавления в код Прюфера первого элемента, лист с минимальным номером удаляется из дерева. Далее снова нужно найти лист с минимальным номером и вписать в код Прюфера номер вершины, смежной с ним, после чего удалить этот лист из дерева, и так далее, пока в дереве не останется только две вершины. На этом построение кода Прюфера заканчивается, так как в него уже были добавлены n-2 номера вершины.

Ниже представлен формальный алгоритм, которому на вход подаётся множество вершин V и множество рёбер E. В строке code ← number, в отличии от остальных подобных, выполняется не присваивание, а добавление в конец массива.

Prufer_code(V,E)
  code = []
  while |V|>2 do
    leaf ← min i for i in V if deg(i)=1
    number ← number in V: (leaf,number) in E
    code ← number
    delete leaf from V
  return code

Восстановление дерева по коду Прюфера[править | править вики-текст]

По построению очевидно, что количество вхождений некоторого числа k в код Прюфера ровно на единицу меньше степени соответствующей вершины. Сразу посчитаем и запишем степень каждой вершины. После этого мы можем узнать номера всех листьев и вычислить номер минимального из них. Из построения, следует, что этот лист связан ребром с первой вершиной из кода Прюфера. Таким образом, первое ребро графа найдено.

После нахождения первого ребра следует уменьшить на единицу степени двух его вершин. После нахождения новых рёбер будем делать также, чтобы степени в массиве соответствовали степеням разности исходного графа уже с найденным. Разность двух этих графов будет соответствовать состоянию, в котором находился граф после составления некоторой части кода. Следовательно, к хранящимся степеням можно заново применить тот же ход --- найти лист с минимальным номером, и определить, что он соединён ребром со следующим элементом кода. Далее опять уменьшить степень каждой из соединённых вершин, и повторить ту же процедуру, и так далее...

Когда представленный алгоритм пройдёт все элементы кода Прюфера, в массиве степеней останутся единицы в двух местах и нули во всех остальных. Следовательно, нужно соединить ребром две вершины с оставшимися единичными степенями, получив последнее n-1-ое ребро.

Как для составления кода Прюфера по графу, так и для обратного преобразования, существуют алгоритмы, работающие за линейное от количество вершин время, то есть с асимптотической сложностью O(n).[1]

Примечания[править | править вики-текст]

Литература[править | править вики-текст]