Prüfer-kód

Számozott fa, melynek Prüfer kódja: 4445.

A gráfelméletben egy számozott fa Prüfer-kódja egy n-2 vagy n-1 (csak megállapodás kérdése) hosszú számsorozat, melyet az alábbi szabály szerint rendelünk a 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 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.

Püfer kód C++ban: Csak egy példa a prüfer kód kidolgozására C++ban

Bemenő állomány: "GRÁF3.BE" A következő képpen néz ki a bemenő állomány:

11
1 1 1 1 1 1 1 2 3 4 4

#include <iostream.h>
#include <conio.h>
#include <stdio.h>
#include <fstream.h>
int n,a[10],k=0;
ifstream f("graf3.be");
void kiolvas()
{ int i,x;
  f>>n;
  for(i=1;i<code><=</code>n;i++)
     { f>>x;
       a[i]=x;
     }
}
 
void kiir()
{ int i;
  for(i=1;i<code><=</code>n;i++)
    cout<<a[i]<<" ";
}
 
void ellenoriz()
{ int i,sz=0;
   for(i=0;i<code><=</code>n;i++)
      sz+=a[i];
   if(sz==2*n-2)
       { cout<<"a sorozat lehet fa";
          k++;
       }
   else
       cout<<"a sorozat nem lehet fa";
}
 
void pruuff()
{ int i;
 for(i=1;i<n;i++)
    for(int j=i+1;j<code><=</code>n;j++)
       if(a[j]!=1&&(a[i]==1))
         { cout<<j<<" ";
           a[i]=0;
           a[j]=a[j]-1;
         }
}
 
void main()
{ clrscr();
   kiolvas();
   kiir();
   cout<<endl;
   ellenoriz();
   cout<<endl;
   if(k!=0)
     pruuff();
   getch();
}

Története

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

Hivatkozások

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