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

Из Википедије, слободне енциклопедије
Jump to navigation Jump to search

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

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

Секвенца се може генерисати тако што се итеративно одузимају чворови дрвета све док не остану само два. Конкретно, ако постоји означено дрво Т са чворовима {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 nlength[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 (зваћемо их у и в). На крају додај грану (у, в) дрвету. [2]

15 uv ← 0
16 for each node i in T
17     if degree[i] = 1
18         then if u = 0
19             then ui
20             else vi
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 који је дрећен за сваки чвор је једнак мултиномијалном коефицијенту.
Доказ се налази при опажању да у Пруферовој секвенци број i се појављује (di – 1) пута.
  • Кајлијева формула може да се генерализује: означено дрво је у ствари разапињуће стабло изведено из комплетан графа. Ако поставимо рестрикцију на набројане Пруферова секвенце, сличне методе могу да дају број разапињућих стабала једног комплетног бипартитивног графа. Ако је G комплетан бипартитвни граф са чворовима 1 до n1 у једној партицији и чворове n1 + 1 до n у другој партицији, број означених разабињућих стабала од графа G је n1^n2-1 n2^n1-1 где је n2 = n − n1.
  • Генерисањем униформних распоређених насумичних Пруферових секвенци и пребацивањем истих у одговаралућа стабла је једноставан метод за генерисање униформних распоређених насумичних означених стабала.

Референце[уреди]

  1. Prüfer, H. (1918).
  2. Jens Gottlieb, Bryant A. Julstrom, Günther R. Raidl, and Franz Rothlauf. (2001).

Спољашње везе[уреди]