В комбинаторной математике , то последовательность прюферово (также прюферовы коды или прюферовы номер ) из меченого дерева является уникальной последовательностью , связанной с деревом. Последовательность дерева на n вершинах имеет длину n - 2 и может быть сгенерирована простым итерационным алгоритмом. Последовательности Прюфера были впервые использованы Хайнцем Прюфером для доказательства формулы Кэли в 1918 году [1].
Алгоритм преобразования дерева в последовательность Прюфера
Можно сгенерировать последовательность Прюфера помеченного дерева, итеративно удаляя вершины из дерева, пока не останутся только две вершины. В частности, рассмотрим помеченное дерево T с вершинами {1, 2, ..., n }. На шаге i удалите лист с наименьшей меткой и установите i- й элемент последовательности Прюфера как метку соседа этого листа.
Последовательность Прюфера помеченного дерева уникальна и имеет длину n - 2.
И кодирование, и декодирование можно свести к целочисленной сортировке по основанию системы счисления и распараллелить. [2]
Пример
Рассмотрим приведенный выше алгоритм, работающий на дереве, показанном справа. Первоначально вершина 1 - это лист с наименьшей меткой, поэтому она сначала удаляется, а 4 помещается в последовательность Прюфера. Следующими удаляются вершины 2 и 3, поэтому 4 добавляется еще дважды. Вершина 4 теперь является листом и имеет наименьшую метку, поэтому она удаляется, и мы добавляем 5 к последовательности. У нас осталось только две вершины, поэтому мы останавливаемся. Последовательность дерева {4,4,4,5}.
Алгоритм преобразования последовательности Прюфера в дерево
Позвольте {a[1], a[2], ..., a[n]}
быть последовательность Прюфера:
В дереве будут n+2
узлы, пронумерованные от 1
до n+2
. Для каждого узла установите его степень равной количеству раз, которое он появляется в последовательности плюс 1. Например, в псевдокоде:
Преобразование Прюфера в дерево ( а ) 1 n ← длина [ a ] 2 T ← граф с n + 2 изолированными узлами, пронумерованными от 1 до n + 2 3 степень ← массив целых чисел 4 для каждого узла i в T - 5 градусов [ i ] ← 1 6 для каждого значения I в сделать 7 степень [ я ] ← степень [ я ] + 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 u ← v ← 016 для каждого узла i в T 17, если степень [ i ] = 1, то 18, если u = 0, то 19 u ← i 20 else 21 v ← i 22 break 23 Вставить ребро [ u , v ] в T 24 степень [ u ] ← степень [ u ] - 125 градус [ v ] ← градус [ v ] - 126 возврат T
Формула Кэли
Последовательность Прюфера помеченного дерева на n вершинах - это уникальная последовательность длины n - 2 на метках от 1 до n . Для заданной последовательности S длины п -2 на этикетках 1 до п , существует уникальное меченное дерево, прюферова последовательность S .
Непосредственным следствием является то, что последовательности Прюфера обеспечивают взаимно однозначное соответствие между набором помеченных деревьев на n вершинах и набором последовательностей длины n - 2 на метках от 1 до n . Последнее множество имеет размер n n −2 , так что существование этой биекции доказывает формулу Кэли , т.е. что существует n n −2 помеченных деревьев на n вершинах.
Другие приложения [4]
- Формулу Кэли можно усилить, чтобы доказать следующее утверждение:
- Количество остовных деревьев в полном графе со степенью указывается для каждой вершины равен полиномиальному коэффициенту
- Доказательство следует из наблюдения, что в порядковом номере Прюфера появляется точно раз.
- Формулу Кэли можно обобщить: помеченное дерево на самом деле является остовным деревом помеченного полного графа . Налагая ограничения на нумерованные последовательности Прюфера, аналогичные методы могут дать количество остовных деревьев полного двудольного графа . Если G - полный двудольный граф с вершинами от 1 до n 1 в одном разбиении и вершинами от n 1 + 1 до n в другом разбиении, количество помеченных остовных деревьев G равно, где n 2 = n - n 1 .
- Генерация равномерно распределенных случайных последовательностей Прюфера и преобразование их в соответствующие деревья - это простой метод генерации равномерно распределенных случайных помеченных деревьев.
Рекомендации
- ^ Прюфер, Х. (1918). "Neuer Beweis eines Satzes über Permutationen". Arch. Математика. Phys . 27 : 742–744.
- ^ Каминити, С., Финокки, И., Петрески, Р. (2007). «О кодировании меченых деревьев». Теоретическая информатика . 382 (2): 97–108. DOI : 10.1016 / j.tcs.2007.03.009 .CS1 maint: несколько имен: список авторов ( ссылка )
- ^ Йенс Готтлиб; Брайант А. Джулстрем; Гюнтер Р. Райдл; Франц Ротлауф. (2001). «Числа Прюфера: плохое представление остовных деревьев для эволюционного поиска» (PDF) . Труды конференции по генетическим и эволюционным вычислениям (GECCO-2001) : 343–350. Архивировано из оригинального (PDF) 26 сентября 2006 года.
- ^ Кадзимото, Х. (2003). «Расширение кода Прюфера и сборка связанных графов из их блоков». Графы и комбинаторика . 19 : 231–239. DOI : 10.1007 / s00373-002-0499-3 .
Внешние ссылки
- Код Прюфера - из MathWorld