Prüfer-kode

I 1918 viste den tyske matematiker Heinz Prüfer en bijektiv korrespondance mellem et træ med knudemængden {1,2, ... , n} og mængden af ord af længde n-2 i symbolerne {1,2, ... ,n}. Disse træbeskrivelser kaldes Prüfer-koder.

Der findes to forskellige algoritmer. Den ene finder koden for et træ, og den anden konstruerer træet ud fra en given kode. Disse to algoritmer er hinandens inverse.

Algoritmen (Fra træ til Prüfer-kode)

Lad T være et træ med knudemængde {1,2, ... , n}. Gennemfør nedenstående punkter 1-3:

1. Find den mindste knude af valens 1, kald den v. Lad w være den knude forbundet med v.
2. Skriv w ned og slet knuden v, samt kanten vw.
3. Hvis der i træet findes mere end 1 kant, gå til punkt 1: ellers stop.

Den resulterende liste af tallene skrevet ned er Prüfer-koden for T.

Eksempel: Dette eksempel illustrere algoritmen på træet T med 6 knuder. Prüfer-koden er tallet 2332.

Algoritmen (Fra Prüfer-kode til træ)

Lad listen af a₁ ... a_n-2 af tal tilfældigt valgt fra mængden {1,..,n}. Gennemfør nedenstående punkter 1-3:

1. Skriv ned den første liste a₁ ... a_n-2; derefter skriv listen 1,2, .. , n.
2. Find det laveste tal, kald det x, som findes i den anden liste men ikke i den første. Slet det første tal i den første liste, kald dette tal for y; slet derefter tallet x fra den anden liste og tegn kanten xy.
3. Hvis den første liste ikke er tom, gå til punkt 2. Ellers er den første liste tom, hvilket vil sige at den anden liste indeholder kun 2 tal tilbage. Tilføj kanten bestående af de to tal til træet: derefter stop.

Eksempel: Dette eksempel illustrerer algoritmen på Prüfer-koden 2332.