Pruferova sekvenca

U oblasti kombinatorna matematika, Pruferova sekvenca (Pruferovi brojevi ili Pruferov kod) označenog stabla je jedinstvena niz vezana za stablo (teorija grafova). To je sekvenca za drvo koje je n veličine ima dužinu n – 2 i može biti generisana pomoću jednostvanog iterativnog algoritma. Pruferovu sekvencu je napravio Hajnc Prufer da bi dokazao Kajlijevu formulu 1918. godine.

Algoritam za prebacivanje drveta u Pruferovu sekvencu

Sekvenca se može generisati tako što se iterativno oduzimaju čvorovi drveta sve dok ne ostanu samo dva. Konkretno, ako postoji označeno drvo T sa čvorovima {1, 2, ..., n}. Na koraku i, skini list sa najmanjom vrednošću i postavi i-ti element sekvence da bude oznaka suseda tog lista.

Pruferova sekvenca je jedinstvena i ima dužinu od n − 2.

Primer

Označeno drvo sa Pruferovom sekvencom {4,4,4,5}.

Razmatramo objašnjeni algoritam iznad da radi na drvetu desno. Inicijalno, čvor 1 je list sa najmanjom oznakom, tako da je on prvi izbačen i 4 se stavlja u Pruferovu sekvencu. Čvorovi 2 i 3 su sledeći sklonjeni, tako da se 4 dodaje još dva puta. Čvor 4 je sada list sa najmanjom oznakom, tako da se uklanja i dodajemo 5 u sekvencu. Ostalo je samo dva čvora tako da se tu zaustavlja algoritam. Sekvenca je na kraju: {4, 4, 4, 5}.

Algoritam koji prebacuje Pruferovu sekvencu u drvo

Neka je {a[1], a[2], ..., a[n]} jedna Pruferoca sekvenca:

Drvo će imati n+2 čvorova, koji su obeleženi od 1 do n+2. Za svaki čvor postavi njegov stepen prema broju koliko puta se ponavlja u sekvenci plus 1. Na primer u pseudo kodu:

 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

Dalje, za svaki broj u sekvenci a[i], nađi prvi (sa najmanjim brojem) čvor j, sa stepenom jedankim 1, dodaj granu (j, a[i]) drvetu, i dekrementiraj stepene j i a[i]. U pseudo kodu:

 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

Na kraju ove petlje ostaće dva čvora sa stepenom 1 (zvaćemo ih u i v). Na kraju dodaj granu (u, v) drvetu.

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

Kajlijeva formula

Pruferova sekvenca označenog drveta sa odeđenim brojem čvorova je jedinstvena sekvenca dužine n -2 sa oznakama 1 do n — toliko je jasno. Donekle manje očigledno je činjenica da za zadatu sekvencu S dužine n -2 sa ozanakama 1 do n, postoji jedinstveno označeno drvo čija je Pruferova sekvenca jeste S.

Posledica toga je da Pruferova sekvenca daje bijekciju između grupe označenih stabala sa n čvorova i grupe sekvenci dužine n -1 na oznakama od 1 do n. Poslednja navedena grupa ima veličinu od  n na n-2, tako da postojanje ove bijekcije dokazuje Kajlijevu formulu tj. Da postoji nn-2 ozančenih stabala na n čvorova.

Ostale primene 

• Kajlijeva formula može da se unapredi da bi se dokazalo sledeće tvrđenje:

Broj stabala u kompletnom grafu Kn sa stepenom di koji je drećen za svaki čvor je jednak multinomijalnom koeficijentu.

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

Dokaz se nalazi pri opažanju da u Pruferovoj sekvenci broj i se pojavljuje (di – 1) puta.

• Kajlijeva formula može da se generalizuje: označeno drvo je u stvari razapinjuće stablo izvedeno iz kompletan grafa. Ako postavimo restrikciju na nabrojane Pruferova sekvence, slične metode mogu da daju broj razapinjućih stabala jednog kompletnog bipartitivnog grafa. Ako je G kompletan bipartitvni graf sa čvorovima 1 do n1 u jednoj particiji i čvorove n1 + 1 do n u drugoj particiji, broj označenih razabinjućih stabala od grafa G je n1^n2-1 n2^n1-1 gde je n2 = n − n1.
• Generisanjem uniformnih raspoređenih nasumičnih Pruferovih sekvenci i prebacivanjem istih u odgovaraluća stabla je jednostavan metod za generisanje uniformnih raspoređenih nasumičnih označenih stabala.

Spoljašnje veze

• Prüfer code – from MathWorld