Пруферова секвенца

У области комбинаторна математика, Пруферова секвенца (Пруферови бројеви или Пруферов код) означеног стабла је јединствена низ везана за стабло (теорија графова). То је секвенца за дрво које је n величине има дужину n – 2 и може бити генерисана помоћу једностваног итеративног алгоритма. Пруферову секвенцу је направио Хајнц Пруфер да би доказао Кајлијеву формулу 1918. године.

Алгоритам за пребацивање дрвета у Пруферову секвенцу

Секвенца се може генерисати тако што се итеративно одузимају чворови дрвета све док не остану само два. Конкретно, ако постоји означено дрво Т са чворовима {1, 2, ..., n}. На кораку i, скини лист са најмањом вредношћу и постави i-ти елемент секвенце да буде ознака суседа тог листа.

Пруферова секвенца је јединствена и има дужину од n − 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 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 (зваћемо их у и в). На крају додај грану (у, в) дрвету.

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

Кајлијева формула

Пруферова секвенца означеног дрвета са одеђеним бројем чворова је јединствена секвенца дужине n -2 са ознакама 1 до n — толико је јасно. Донекле мање очигледно је чињеница да за задату секвенцу С дужине n -2 са озанакама 1 до n, постоји јединствено означено дрво чија је Пруферова секвенца јесте С.

Последица тога је да Пруферова секвенца даје бијекцију између групе означених стабала са n чворова и групе секвенци дужине n -1 на ознакама од 1 до n. Последња наведена група има величину од  n на n-2, тако да постојање ове бијекције доказује Кајлијеву формулу тј. Да постоји nn-2 озанчених стабала на n чворова.

Остале примене 

• Кајлијева формула може да се унапреди да би се доказало следеће тврђење:

Број стабала у комплетном графу Кn са степеном di који је дрећен за сваки чвор је једнак мултиномијалном коефицијенту.

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

Доказ се налази при опажању да у Пруферовој секвенци број i се појављује (di – 1) пута.

• Кајлијева формула може да се генерализује: означено дрво је у ствари разапињуће стабло изведено из комплетан графа. Ако поставимо рестрикцију на набројане Пруферова секвенце, сличне методе могу да дају број разапињућих стабала једног комплетног бипартитивног графа. Ако је G комплетан бипартитвни граф са чворовима 1 до n1 у једној партицији и чворове n1 1 до n у другој партицији, број означених разабињућих стабала од графа G је n1^n2-1 n2^n1-1 где је n2 = n − n1.
• Генерисањем униформних распоређених насумичних Пруферових секвенци и пребацивањем истих у одговаралућа стабла је једноставан метод за генерисање униформних распоређених насумичних означених стабала.

Спољашње везе

• Prüfer code – from MathWorld