Немає перевірених версій цієї сторінки ймовірно її ще не перевіряли на відповідність правилам проекту Послідовність Прюф

Немає цієї сторінки; ймовірно, її ще не перевіряли на відповідність правилам проекту.

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

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

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

Приклад в графах

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

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

Для відновлення дерева за послідовністю p=(p₁,...,p_n-2), створений список номерів вершин s=(1,...,n). Вибрано перший номер i₁, який не зустрічається в послідовності. Додано ребро (i₁,p₁), після цього видалено i₁ з s і p₁ з p. Процес повторюється до моменту, коли послідовність p стає порожнім. У цей момент список s містить рівно два числа і_n-1 і n. Залишається додати ребро (i_n-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)

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 }

Інші приклади

З послідовності Прюфера випливає Формула Келі, тобто число кістякових дерев повного графу $\pi$ _n з n вершинами рівне n^n-2. Доказ випливає з того, що код Прюфера дає бієкцію б між кістяковими деревами та послідовністю довжин n-2 з числа n чисел.
Послідовність Прюфера також дозволяє узагальнити формулу Келі в разі, якщо дана ступінь вершин, якщо (d₁,...,d_n) це послідовність ступеня дерева, то число дерев з такими ступенями рівне мультиномінальному коефіцієнту:

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

Примітки

Prüfer, H. (1918). Neuer Beweis eines Satzes über Permutationen. Arch. Math. Phys. 27: 742—744.
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 має пустий невідомий параметр: |df= ()

[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 має пустий невідомий параметр: |df= ()