Pruferova sekvenca

Iz Vikipedije, slobodne enciklopedije
Idi na navigaciju Idi na pretragu

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.[1]

Algoritam za prebacivanje drveta u Pruferovu sekvencu[uredi]

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[uredi]

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[uredi]

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 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

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. [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

Kajlijeva formula[uredi]

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 [uredi]

  • 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.
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.

Reference[uredi]

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

Spoljašnje veze[uredi]