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

Послідовність Прюфера (або ж код Прюфера) у комбінаторній математиці є унікальною послідовністю, пов'язаною з деревом. Послідовність дерева з n вершин має довжину n - 2, і може бути сформована простим ітераційним алгоритмом. Послідовність Прюфера вперше використав Хайнц Прюфе, щоб довести формулу Келі в 1918 році.^[1]

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

Нехай 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 T
10          if degree[j] = 1
11             then 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)^[2]

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

C++ реалізація

Код функції

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.] (рос.)

Примітки

1. Prüfer, H. (1918). Neuer Beweis eines Satzes über Permutationen. Arch. Math. Phys. 27: 742—744.
2. Jens Gottlieb; Bryant A. Julstrom; Günther R. Raidl; Franz Rothlauf. (2001). Prüfer numbers: A poor representation of spanning trees for evolutionary search (PDF). Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001): 343—350. Архів оригіналу (PDF) за 26 вересня 2006. {{cite journal}}: Cite має пустий невідомий параметр: |df= (довідка)