jobbra|frame|Számozott fa, melynek Prüfer kódja: 4445. A gráfelméletben egy n csúcsú számozott fa Prüfer-kódja egy n–2 hosszú számsorozat, melyet a későbbiekben részletezett szabály szerint rendelünk a fához. (A kód tulajdonképpen n–1 hosszúságú, csak az utolsó elem elhagyható, mert az mindig n.)
Prüfer-kód hozzárendelése számozott fához
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 v1. 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 v1,v2,...,vn-2 számsorozat a fa Prüfer-kódja.
Algoritmus: Számozott fából Prüfer-kód 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:
none|frame
Számozott fából Prüfer-kód C++-ban /* graf0.be tartalma pl. az ábra szerint: 6 1 4 2 4 3 4 4 5 5 6 */
// Számozott fából Prüfer-kód
#include <iostream> #include <fstream>
int n, m, a, b, fok;
// Bemeneti állomány: csúcsok száma, majd élek végpontjai (szóközzel elválasztva) std::ifstream f("graf0.be");
// Adatok beolvasása void olvas() { int i; f >> n; m = n - 1;
// Fokszámok nullázása for (i = 1; i <= n; i++) fok[i] = 0;
// Élek beolvasása, fokszámok kiszámítása for(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ése while ( (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ása if (a[k] == j) std::cout << b[k] << " "; else std::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; }
Számozott fa hozzárendelése Prüfer-kódhoz 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) 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:
44456 (1,4) él44561 (2,4) él45612 (3,4) él56123 (4,5) él61234 (5,6) él
Prüfer-kódból számozott fa (1. módszer) C++-ban /* graf.be tartalma pl. az ábra szerint: 4 4 4 4 5 */
// Prüfer-kódból számozott fa
#include <iostream> #include <fstream>
int n, m, a;
// Bemeneti állomány: kód hossza, majd a kód elemei (szóközzel elválasztva) std::ifstream f("graf.be");
// Adatok beolvasása void olvas() { int i; f >> n; for(i = 1; i <= n; i++) f >> a[i]; n++; // Az utolsó elem hozzáadása a[n] = n+1;
// A sorozat ellenőrzése void 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 legkisebb szám, amely nincs benne az a[i], ..., a[m] sorozatban min++; j = i; while ((j<=m) && (a[j]!=min)) j++; } while (j <= m); m++; // A legkisebb elem hozzáadása a sorozathoz a[m] = min; // Él kiírása std::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) 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 fi, a Prüfer-kód minden i elemére, növeljük 1-gyel az fi-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 fi és fj értékeket. f-ben két 1-gyel egyenlő elem marad, legyenek ezek fi és fj; 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)
Prüfer-kódból számozott fa (2. módszer) C++-ban /* graf.be tartalma pl. az ábra szerint: 4 4 4 4 5 */
// Prüfer-kódból számozott fa
#include <iostream> #include <fstream>
int n, a, fok;
// Bemeneti állomány: kód hossza, majd a kód elemei (szóközzel elválasztva) std::ifstream f("graf.be");
// Adatok beolvasása void olvas() { int i; f >> n; for (i = 1; i <= n; i++) f >> a[i]; }
// A sorozat ellenőrzése void 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ása void 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ása fok[ a[i] ]--; fok[j]--; break;
k = 1; while ( (k<=n+2) && (fok[k]!=1) ) k++; std::cout << "(" << k << ","; // utolsó él egyik csúcsa k++; 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; }
Története bélyegkép|jobbra|260px|Heinz Prüfer 1930-ban
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.
Források
Katona Gyula Y., Recski András, Szabó Csaba: Gráfelmélet, algoritmuselmélet és algebra, Typotex Kiadó, 2002.
További információk Prüfer-kód vizualizációs applet Wolfram Mathworld
Kategória:Gráfalgoritmusok