Prüfer kód n számozott ponton lévő F fa esetén hagyjuk el a legkisebb indexű elsőfokú pontot, és írjuk fel a szomszédjának számát, legyen az v1. Ismételjük ezt a maradék fával, amíg csak egy pont marad. Ennek indexe biztosan n, hiszen mindig van legalább két elsőfokú pont. Ezt már nem is írjuk le (többnyire).
Def: Az így kapott n-2 hosszú számsorozat v1, v2, v3 .. vn-2 az F fa Prüfer kódja.
A Prüfer kód egyértelműen meghatározza a fát.
A fa csúcsainak száma a kód hossza + 2. Ha egy csúcs indexe k-szor fordul elő, akkor a fokszáma k+1.
Visszafejtés menete:
A leírás sorrendjében (balról jobbra) haladunk végig a kódon. Ha még nincs lerajzolva a csúcs, aminél állunk, lerajzoljuk, és hozzákötjük a legkisebb indexű csúcsot, ami nem szerepel tőle jobbra (lebontáskor ez volt a legkisebb elsőfokú).
(A Prüfer kód mindig n csúcsú, n-1 élű gráfot ad, ha belátjuk, hogy nincs benne kör, akkor biztos, hogy fa az eredmény.
Indirekt tfh van kör az eredményben: x, y, z. Ilyenkor a kódban x, y, z sorrendben kell szerepelniük. y-hoz x-et kötjük, z-hez y-t, viszont x-hez z-t kellene kötni, ami tőle jobbra szerepel.)
Szerzők: yoda
[Szócikk szerkesztése]
[Lexikon kezdőlapra lépés]
|
