Prüfer kode
Fra Wikipedia, den frie encyklopædi
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 udfra en given kode. Disse to algoritmer er hinandens inverse.
[redigér] 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:
- Find den mindste knude af valens 1, kald den v. Lad w være den knude forbundet med v.
- Skriv w ned og slet knuden v, samt kanten vw.
- 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.
[redigér] Algoritmen (Fra Prüfer-kode til træ)
Lad listen af a1 ... an-2 af tal tilfældigt valgt fra mængden {1,..,n}. Gennemfør nedenstående punkter 1-3:
- Skriv ned den første liste a1 ... an-2; derefter skriv listen 1,2, .. , n.
- 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.
- 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.