последовательность Прюфера

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

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

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

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

Как кодирование, так и декодирование можно свести к целочисленной сортировке и распараллелить. ^[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 н ← длина [ а ] 2 T ← граф с n + 2 изолированными узлами, пронумерованными от 1 до  n + 2 3 степень ← массив целых чисел 4 для каждого узла i в T  до 5 степени [ i ] ← 1 6 для каждого значения i в a  do 7 степень [ i ] ← степень [ i ] + 1

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

8 для каждого значения i в a  do 9 для каждого узла j в T  do
10 если  степень [ j ] = 1 , то
11 Вставить ребро [ i , j ] в T
12 степень [ i ] ← степень [ i ] - 113 степень [ j ] ← степень [ j ] - 114 перерыв

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

15 у ← в ← 016 для каждого узла i в T
17 если  степень [ i ] = 1 , то
18 если  u = 0 , то
19 u ← i
20 иначе
21 v ← i
22 разрыв
23 Вставить ребро [ u , v ] в T
24 степень [ u ] ← степень [ u ] - 125 градусов [ v ] ← градусов [ v ] - 126 возврат  Т

Формула Кэли

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

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

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

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

Число остовных деревьев в полном графе со степенью, указанной для каждой вершины, равно мультиномиальному коэффициенту ${\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}$ ${\textstyle d_{i}-1}$

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

Ссылки

1. Прюфер, Х. (1918). «Neuer Beweis eines Satzes über Permutationen». Арх. Математика. Физ . 27 : 742–744.
2. Каминити, С., Финокки, И., Петрески, Р. (2007). «О кодировании помеченных деревьев». Теоретическая информатика . 382 (2): 97–108. doi : 10.1016/j.tcs.2007.03.009 .{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
3. Йенс Готтлиб; Брайант А. Юльстром; Гюнтер Р. Райдл; Франц Ротлауф. (2001). «Числа Прюфера: плохое представление остовных деревьев для эволюционного поиска» (PDF) . Труды конференции по генетическим и эволюционным вычислениям (GECCO-2001) : 343–350. Архивировано из оригинала (PDF) 2006-09-26.
4. Каджимото, Х. (2003). «Расширение кода Прюфера и сборка связанных графов из их блоков». Графы и комбинаторика . 19 (2): 231–239. doi :10.1007/s00373-002-0499-3. S2CID  22970936.

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

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