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

Нехай T є дерево з вершинами, пронумеровані числами {1,2,...,n}. Побудова послідовності Прюфера для дерева T ведеться шляхом послідовного видалення вершин з дерева, поки не залишаться тільки дві вершини. При цьому кожен раз вибирається кінцева вершина з найменшим номером і в послідовність записується номер єдиної вершини, з якою вона з'єднана. В результаті отворюється послідовність (p1,...,pn-2), складену з чисел {1,2,..., n}, можливо з повтореннями.

• Для дерева на діаграмі вершина 1 є кінцевою вершиною з найменшим номером, тому вона видаляється і 4 ставиться в послідовність Прюфера.
• Вершини 2 і 3 видаляються в наступному, так що 4 додається двічі.
• Вершина 4 Тепер стала кінцевою і має найменший номер, тому вона видаляється і додається 5 до послідовності.
• Залишається лише з двома вершинами, тому завершуються подальші перетворення.
• В результаті послідовність Прюфера (4,4,4,5).

Для відновлення дерева за послідовністю p=(p1,...,pn-2), створений список номерів вершин s=(1,...,n). Вибрано перший номер i1, який не зустрічається в послідовності. Додано ребро (i1,p1), після цього видалено i1 з s і p1 з p.Процес повторюється до моменту, коли послідовність p стає порожнім. У цей момент список s містить рівно два числа іn-1 і n. Залишається додати ребро (in-1,n), і дерево побудовано.

Нехай {a [1], a [2], ..., a [n]} буде послідовністю Прюфера:

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

 0 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 5     do degree[i] ← 1 6 for each value i in a 7     do degree[i] ← degree[i] + 1

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

 8 for each value i in a 9     for each node j in T10          if degree[j] = 111             then Insert edge[i, j] into T12                  degree[i] ← degree[i] - 113                  degree[j] ← degree[j] - 114                  break

Наприкінці цього циклу залишиться два вузли з ступенем 1 (називайте їх u, v). Нарешті, додати до дерева край (u,v)^[2]

15 u ← v ← 016 for each node i in T17     if degree[i] = 118         then if u = 019             then u ← i20             else v ← i21                  break22 Insert edge[u, v] into T23 degree[u] ← degree[u] - 124 degree[v] ← degree[v] - 125 return T

0 #include<bits/stdc++.h> 1 using namespace std;2 void printTreeEdges(int prufer[], int m) 3 { 4    int vertices = m + 2; 5    int vertex_set[vertices];6    for (int i=0; i<vertices-2; i++) 7       vertex_set[prufer[i]-1] += 1;   8    cout<<"\nThe edge set E(G) is :\n"; 9    int j = 0; 10   for (int i=0; i<vertices-2; i++) 11   { 12       for (j=0; j<vertices; j++) 13       {  14           if (vertex_set[j] == 0) 15           {  16               vertex_set[j] = -1; 17               cout << "(" << (j+1) << ","18                    << prufer[i] << ")  "; 19               vertex_set[prufer[i]-1]--; 20               break; 21           } 22       } 23   } 24   for (int i=0; i<vertices; i++ ) 25   { 26       if (vertex_set[i] == 0 && j == 0 ) 27       { 28           cout << "(" << (i+1) << ","; 29           j++; 30       } 31       else if (vertex_set[i] == 0 && j == 1 ) 32           cout << (i+1) << ")\n"; 33   } 34 }

0 int main() 1 { 2   int prufer[] = {4, 1, 3, 4}; 3   int n = sizeof(prufer)/sizeof(prufer[0]); 4   printTreeEdges(prufer, n); 5   return 0; 6 }

• З послідовності Прюфера випливає Формула Келі, тобто число кістякових дерев повного графу ${\displaystyle \pi }$ n з n вершинами рівне nn-2. Доказ випливає з того, що код Прюфера дає бієкцію б між кістяковими деревами та послідовністю довжин n-2 з числа n чисел.
• Послідовність Прюфера також дозволяє узагальнити формулу Келі в разі, якщо дана ступінь вершин, якщо (d1,...,dn) це послідовність ступеня дерева, то число дерев з такими ступенями рівне мультиномінальному коефіцієнту:

${\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)!}}.}$

• Код Прюфера використовується для побудови випадкових дерев.

• Prüfer code [Архівовано 2 червня 2021 у Wayback Machine.] на сайті MathWorld (англ.)
• Prufer Code to Tree Creation [Архівовано 17 листопада 2018 у Wayback Machine.] (англ.)
• Коды Прюфера [Архівовано 1 грудня 2018 у Wayback Machine.] (рос.)