Prüfer-kód

Tekintsünk egy tetszőleges fát az {1,2…n} csúcsokon, és rendeljünk hozzá egy számsorozatot a következőképpen: Hagyjuk el a fa elsőfokú csúcsai közül azt, amelyiknek a legkisebb a sorszáma, és közben annak a csúcsnak írjuk fel a sorszámát, amellyel az elhagyott csúcs össze volt kötve. Legyen ez v₁. Ezt ismételjük, amíg már csak egy csúcs marad. Nyilvánvaló, hogy ez a csúcs az n-edik sorszámú, hiszen egy fának mindig van legalább 2 elsőfokú csúcsa, és n-nél csak kisebb sorszámú csúcsok vannak, így előbb azokat hagyjuk el. Ezért a számsorozat végén nem is kell szerepelnie, hiszen egyértelmű. Az így kapott v₁,v₂,…,v_n-2 számsorozat a fa Prüfer-kódja.

Algoritmus: Számozott fából Prüfer-kód szerkesztés

• Bemenet egy számozott fa (csúcsait az 1, 2, ..., n számokkal címkézzük meg)
• Végezzük el az alábbiakat mindaddig, amíg egyetlen él marad

• válasszuk ki a legkisebb számú levelet (fokszáma 1),
• írjuk ki a vele szomszédos csúcs számát,
• töröljük a fából a kiválasztott csúcsot (természetesen a hozzáilleszkedő éllel együtt).

• Az eredményül kapott számok a kiírás sorrendjében képezik a Prüfer-kódot.

A mellékelt ábrán
a legkisebb értékű levél az 1, tehát kiírjuk a 4-et, törüljük az 1-et
most legkisebb értékű levél a 2, kiírjuk a 4-et, töröljük a 2-t,
most legkisebb értékű levél a 3, kiírjuk a 4-et, töröljük a 3-t,
most legkisebb értékű levél a 4, kiírjuk az 5-öt, töröljük a 4-t,
egy él maradt, az (5,6), tehát vége. Eredmény: 4, 4, 4, 5.

Még egy példa:

/* graf0.be tartalma pl. az ábra szerint:61 42 43 44 55 6*/// Számozott fából Prüfer-kód#include <iostream>#include <fstream>int n, m, a[50], b[50], fok[50];// Bemeneti állomány: csúcsok száma, majd élek végpontjai (szóközzel elválasztva)std::ifstream f("graf0.be");// Adatok beolvasásavoid olvas(){int i;f >> n;m = n - 1;// Fokszámok nullázásafor (i = 1; i <= n; i++)fok[i] = 0;// Élek beolvasása, fokszámok kiszámításafor(i = 1; i <= m; i++){f >> a[i];f >> b[i];fok[ a[i] ]++;fok[ b[i] ]++;}} void pruefer(){int i,j,k;for (i = 1; i <= n-2; i++){j = 1;// Legkisebb számú levél keresésewhile ( (j<=n) && (fok[j]!=1) )j++;k = 1;while ( (k<=m) && (a[k]!=j) && (b[k]!=j )  )k++;// Kód újabb elemének kiírásaif (a[k] == j)std::cout << b[k] << " ";elsestd::cout << a[k] << " ";fok[ a[k] ]--;fok[ b[k] ]--;a[k]=0;b[k]=0;}} int main(){ olvas();std::cout << std::endl;pruefer();std::cout << std::endl;return 0;}

Az első módszer alapötlete a következő: Hozzáadjuk a Prüfer-kódhoz utolsó elemként az n-et. Kiválasztjuk azt a legkisebb pozitív természetes számot, amelyik nem szerepel a sorozatban (Prüfer-kód, és n). A létrehozandó fában összekötjük ezt a számot a sorozat első elemével. Ezt a legkisebb számot hozzáadjuk a sorozathoz, majd töröljük a sorozat első elemét. Ezt a folyamatot addig folytatjuk, ameddig el nem fogynak az eredeti sorozat elemei.

Algoritmus: Prüfer-kódból számozott fa (1. módszer) szerkesztés

• Bemenet: egy n-2 elemű Prüfer-kód, amelyhez hozzáadjuk az n értéket utolsónak.
• Végezzük el n-1-szer a következőket:

• meghatározzuk azt a legkisebb pozitív természetes számot amelyikhez még nem húztunk élt és nem eleme a sorozatnak,
• kössük össze egy éllel az ezzel a számmal jelölt csúcsot a sorozat első elemével,
• töröljük a sorozat első elmét

• Eredmény: a kapott fa

A mellékelt példa esetében a Prüfer-kód: 4,4,4,5. Az algoritmus lépései:

/* graf.be tartalma pl. az ábra szerint:44 4 4 5*/// Prüfer-kódból számozott fa#include <iostream>#include <fstream>int n, m, a[50];// Bemeneti állomány: kód hossza, majd a kód elemei (szóközzel elválasztva)std::ifstream f("graf.be");// Adatok beolvasásavoid olvas(){int i;f >> n;for(i = 1; i <= n; i++)f >> a[i];n++;// Az utolsó elem hozzáadásaa[n] = n+1;} // A sorozat ellenőrzésevoid ellenoriz(){int i;for (i = 1; i <= n; i++)if (a[i]>n+1){std::cout << "A sorozat nem lehet fa ";exit(1);};}void pruefer(){int i, j, min;m = n;for(i = 1; i <= n; i++){min = 0;do{// A legkisebbb szám, amely nincs benne az a[i], ..., a[m] sorozatbanmin++;j = i;while ((j<=m) && (a[j]!=min))j++;} while (j <= m);m++;// A legkisebb elem hozzáadása a sorozathoza[m] = min;// Él kiírásastd::cout << "(" << min << "," << a[i] << ")" << std::endl;} }int main(){olvas();std::cout << std::endl;ellenoriz();pruefer();return 0;}

A második módszer alapötlete a következő: A Prüfer-kódból kiszámítjuk az egyes csúcsok fokszámát, majd ezek alapján berajzoljuk a fa éleit, mindig levelet (1 fokszámú csúcsot) keresve.

Algoritmus: Prüfer-kódból számozott fa (2. módszer) szerkesztés

• Bemenet: Prüfer-kód
• Kiszámítjuk a csúcsok fokszámát a következőképpen:

• kezdetben minden fokszám 1, az i csúcs fokszámát jelölje f_i,
• a Prüfer-kód minden i elemére, növeljük 1-gyel az f_i-t,

• a Prüfer-kód minden i elemére végezzük el:

• keressük meg az f sorozat első 1-es elemét, legyen ennek a sorszáma j,
• kössük össze egy éllel az i és j csúcsokat,
• csökkentsük 1-gyel az f_i és f_j értékeket.

• f-ben két 1-gyel egyenlő elem marad, legyenek ezek f_i és f_j; kössük össze az i csúcsot a j csúccsal.
• Eredmény: az élekből összeálló fa.

A mellékelt ábra esetében a Prüfer-kód 4,4,4,5, az algoritmus lépései:

A fokszámsorozat: 1,1,1,4,2,1.

Kód: 4,4,4,5
Fokszámsorozat: 1,1,1,4,2,1 él: (1,4)

Kódrész: 4,4,5
Fokszámsorozat: 0,1,1,3,2,1 él: (2,4)

Kódrész: 4,5
Fokszámsorozat: 0,0,1,2,2,1 él: (3,4)

Kódrész: 5
Fokszámsorozat: 0,0,0,1,2,1 él: (4,5)

Kódrész:
Fokszámsorozat: 0,0,0,0,1,1 él: (5,6)

/* graf.be tartalma pl. az ábra szerint:44 4 4 5*/// Prüfer-kódból számozott fa#include <iostream>#include <fstream>int n, a[50], fok[52];// Bemeneti állomány: kód hossza, majd a kód elemei (szóközzel elválasztva)std::ifstream f("graf.be");// Adatok beolvasásavoid olvas(){int i;f >> n;for (i = 1; i <= n; i++)f >> a[i];}// A sorozat ellenőrzésevoid ellenoriz(){int i;for (i = 1; i <= n; i++)if (a[i] > n+1){std::cout << "a sorozat nem lehet fa ";exit(1);};}// Az egyes csúcsok fokszámának kiszámításavoid fokszam(){int i;for (i = 1; i <= n+2; i++)fok[i] = 1;for (i = 1; i <= n; i++)fok[ a[i] ]++;}void pruefer(){int i, j, k;for (i = 1; i <= n; i++)for (j=1; j<=n+2; j++){if (fok[j]==1){std::cout << "(" << j  << "," << a[i] << ")" << std::endl;  // él kiírásafok[ a[i] ]--;fok[j]--;break;}}k = 1;while ( (k<=n+2) && (fok[k]!=1) )k++;std::cout << "(" <<  k << ",";             // utolsó él egyik csúcsak++;while ( (k<=n+2) && (fok[k]!=1) )k++;std::cout <<  k << ")";                // utolsó él másik csúcsa}int main(){olvas();std::cout << std::endl;ellenoriz();fokszam();pruefer();std::cout << std::endl;return 0;}

A Prüfer-kódot először Heinz Prüfer alkalmazta 1918-ban, melynek segítségével bizonyította a Cayley-formulát.

• Prüfer, H. (1918). „Neuer Beweis eines Satzes über Permutationen”. Arch. Math. Phys. 27, 742–744. o.  
• Katona Gyula Y., Recski András, Szabó Csaba: Gráfelmélet, algoritmuselmélet és algebra, Typotex Kiadó, 2002.

• Prüfer-kód vizualizációs applet
• Wolfram Mathworld