Prüfer-kód

A Wikipédiából, a szabad enciklopédiából
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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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

Prufer-kode algoritmen.png


  •  


Számozott fa hozzárendelése Prüfer-kódhoz[szerkesztés | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

  • Bemenet: egy n elemű Prüfer-kód, amelyhez hozzáadjuk az n értéket utolsónak.
  • Végezzük le n-szer a következőket:
  • meghatározzuk azt a legkisebb pozitív természetes számot, amelyik 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:

4 4 4 5 6 (1,4) él
4 4 5 6 1 (2,4) él
4 5 6 1 2 (3,4) él
5 6 1 2 3 (4,5) él
6 1 2 3 4 (5,6) él


  •  


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 | forrásszöveg szerkesztése]

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


  •  


Története[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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

További információk[szerkesztés | forrásszöveg szerkesztése]