Последовательность Прюфера - Prüfer sequence

В комбинаторной математике , то последовательность прюферово (также прюферовы коды или прюферовы номер ) из меченого дерева является уникальной последовательностью , связанной с деревом. Последовательность дерева на n вершинах имеет длину n - 2 и может быть сгенерирована простым итерационным алгоритмом. Последовательности Прюфера были впервые использованы Хайнцем Прюфером для доказательства формулы Кэли в 1918 году.

Алгоритм преобразования дерева в последовательность Прюфера

Можно сгенерировать последовательность Прюфера помеченного дерева, итеративно удаляя вершины из дерева, пока не останутся только две вершины. В частности, рассмотрим помеченное дерево T с вершинами {1, 2, ..., n }. На шаге i удалите лист с наименьшей меткой и установите i- й элемент последовательности Прюфера как метку соседа этого листа.

Последовательность Прюфера помеченного дерева уникальна и имеет длину n - 2.

И кодирование, и декодирование можно свести к целочисленной сортировке по основанию системы счисления и распараллелить.

Пример

Помеченное дерево с последовательностью Прюфера {4,4,4,5}.

Рассмотрим приведенный выше алгоритм, работающий на дереве, показанном справа. Первоначально вершина 1 - это лист с наименьшей меткой, поэтому она сначала удаляется, а 4 помещается в последовательность Прюфера. Следующими удаляются вершины 2 и 3, поэтому 4 добавляется еще дважды. Вершина 4 теперь является листом и имеет наименьшую метку, поэтому она удаляется, и мы добавляем 5 к последовательности. У нас осталось только две вершины, поэтому мы останавливаемся. Последовательность дерева {4,4,4,5}.

Алгоритм преобразования последовательности Прюфера в дерево

Позвольте {a[1], a[2], ..., a[n]}быть последовательность Прюфера:

В дереве будут n+2узлы, пронумерованные от 1до n+2. Для каждого узла установите его степень равной количеству раз, которое он появляется в последовательности плюс 1. Например, в псевдокоде:

 Convert-Prüfer-to-Tree(a)
 1 n ← length[a]
 2 T ← a graph with n + 2 isolated nodes, numbered 1 to n + 2
 3 degree ← an array of integers
 4 for each node i in T do
 5     degree[i] ← 1
 6 for each value i in a do
 7     degree[i] ← degree[i] + 1

Затем для каждого числа в последовательности a[i]найдите первый (с наименьшим номером) узел jсо степенью, равной 1, добавьте ребро (j, a[i])к дереву и уменьшите степени jи a[i]. В псевдокоде:

 8 for each value i in a do
 9     for each node j in T do
10         if degree[j] = 1 then
11             Insert edge[i, j] into T
12             degree[i] ← degree[i] - 1
13             degree[j] ← degree[j] - 1
14             break

В конце этого цикла останутся два узла со степенью 1 (назовем их u, v). Наконец, добавьте край (u,v)к дереву.

15 u ← v ← 0
16 for each node i in T
17     if degree[i] = 1 then
18         if u = 0 then
19             u ← i
20         else
21             v ← i
22             break
23 Insert edge[u, v] into T
24 degree[u] ← degree[u] - 1
25 degree[v] ← degree[v] - 1
26 return T

Формула Кэли

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

Непосредственным следствием является то, что последовательности Прюфера обеспечивают взаимно однозначное соответствие между набором помеченных деревьев на n вершинах и набором последовательностей длины n - 2 на метках от 1 до n . Последнее множество имеет размер n ^{n −2} , так что существование этой биекции доказывает формулу Кэли , т.е. что существует n ^{n −2} помеченных деревьев на n вершинах.

Другие приложения

Формулу Кэли можно усилить, чтобы доказать следующее утверждение:

Количество остовных деревьев в полном графе со степенью, указанной для каждой вершины , равно полиномиальному коэффициенту

{\ displaystyle K_ {n}}

{\ displaystyle d_ {i}}

{\ displaystyle i}

{\ displaystyle {\ binom {n-2} {d_ {1} -1, \, d_ {2} -1, \, \ dots, \, d_ {n} -1}} = {\ frac {(n -2)!} {(D_ {1} -1)! (D_ {2} -1)! \ Cdots (d_ {n} -1)!}}.}

Доказательство следует из наблюдения, что порядковый номер Прюфера встречается ровно раз.

{\ displaystyle i}

{\ displaystyle (d_ {i} -1)}

Формулу Кэли можно обобщить: помеченное дерево на самом деле является остовным деревом помеченного полного графа . Налагая ограничения на пронумерованные последовательности Прюфера, аналогичные методы могут дать количество остовных деревьев полного двудольного графа . Если G - полный двудольный граф с вершинами от 1 до n ₁ в одном разбиении и вершинами от n ₁ + 1 до n в другом разбиении, количество помеченных остовных деревьев G равно , где n ₂ = n - n ₁ . ${\ displaystyle n_ {1} ^ {n_ {2} -1} n_ {2} ^ {n_ {1} -1}}$
Генерация равномерно распределенных случайных последовательностей Прюфера и преобразование их в соответствующие деревья - это простой метод генерации равномерно распределенных случайных помеченных деревьев.

Внешние ссылки

Код Прюфера - из MathWorld

Languages

In other projects