Új szócikk írása

Szöveg:

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).<br /> <br /> Def: Az így kapott n-2 hosszú számsorozat v₁, v₂, v₃ .. v_n-2 az F fa Prüfer kódja.<br /> <br /> A Prüfer kód egyértelműen meghatározza a fát.<br /> 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.<br /> Visszafejtés menete: <br /> 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ú).<br /> (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.<br /> 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.)<br />

Neved: