Prüfer-koding

I matematikk er Prüfer-koding en metode for kompakt å beskrive et tre med nummererte hjørner. Denne kodingen representerer et tre med n nummererte hjørner med en sekvens av n-2 termer. En gitt sekvens P tilsvarer ett og bare ett tre nummerert fra 1 til n . $P = (x_ {1}, x_ {2}, x_ {3}, ..., x _ {{n-2}})$

Prüfer-sekvenser ble først brukt av Heinz Prüfer for å demonstrere Cayleys formel i 1918. De kan også brukes i dataprogrammering for å registrere strukturen til et tre mer kompakt enn med pekere .

Koding

Merk: alle eksemplene som følger refererer til treet T motsatt.

Algoritme

Prüfer-sekvensen er bygget med følgende algoritme :

Données : Arbre T Tant qu'il reste plus de deux sommets dans l'arbre T Identifier la feuille v de l'arbre ayant le numéro minimum Ajouter à la suite P le seul sommet s adjacent à v dans l'arbre T Enlever de l'arbre T le sommet v et l'arête incidente à v Fin Tant que

Eksempel

Tenk på treet i figuren ovenfor.

I begynnelsen er 1 arket med minimumstall , det er altså det man trekker seg først, og man setter 4 (nummeret på grenen det var koblet til) i fortsettelsen av Prüfer.

Vertices 2 og 3 er den neste som skal fjernes, og vi legger til to ganger til 4 i Prüfer-sekvensen.

Vertex 4 er nå et blad og har det laveste tallet, så vi fjerner det og legger til 5 (grenen det var festet til) på slutten av suiten.

Det er bare to hjørner igjen, så vi stopper. Prüfer-sekvensen som koder for treet er . $P = (4,4,4,5)$

Dekoding - Første metode

Denne algoritmen er basert på en sekvens av grader fra hvert toppunkt i treet . $D$ $T$

Algoritme

Treet kan rekonstrueres ved hjelp av følgende inverse algoritme:

Données : suite de Prüfer P de longueur n – 2 Créer un graphe T composé de n sommets isolés numérotés de 1 à n Créer une suite D composée de n valeurs toutes à 1, appelées degrés Pour chaque valeur xi de P Augmenter de 1 le degré du sommet numéroté xi dans D Fin Pour chaque Pour chaque valeur xi de P Trouver le sommet de degré 1 qui a le plus petit numéro, soit j ce numéro Ajouter l'arête allant de xi en j au graphe T Diminuer de 1 les degrés de xi et de j dans D Fin Pour chaque Ajouter l'arête reliant les deux sommets restants de degré 1

Eksempel

Tenk på følgende . Det må tillate oss å rekonstruere treet i figuren ovenfor. $P = (4,4,4,5)$

I en første fase lager vi en graf med seks isolerte hjørner nummerert fra 1 til 6. Vi tillegger dem alle en standardgrad lik 1. Deretter krysser vi P ved å øke graden av hjørnene som vises der: vi øker tre ganger graden av toppunkt 4 og en gang graden av toppunkt 5. Til slutt har vi gradene D = (1, 1, 1, 4, 2, 1).

I neste fase går vi gjennom P igjen:

For x 1 = 4 ser vi etter toppunktet med det laveste antall grader lik 1. Det er toppunktet 1 og vi forbinder toppunktene 1 og 4, mens vi reduserer gradene. Vi har nå gradene D = (0, 1, 1, 3, 2, 1).
For x 2 = 4 ser vi etter toppunktet med det laveste antall grader lik 1. Det er toppunktet 2 og vi forbinder toppunktene 2 og 4, mens vi reduserer gradene. Vi har nå gradene D = (0, 0, 1, 2, 2, 1).
For x 3 = 4 ser vi etter toppunktet med det laveste antall grader lik 1. Det er toppunktet 3 og vi forbinder toppunktene 3 og 4, mens vi reduserer gradene. Vi har nå gradene D = (0, 0, 0, 1, 2, 1).
For x 4 = 5 ser vi etter toppunktet med det laveste antall grader lik 1. Det er toppunktet 4 og vi forbinder toppunktene 4 og 5, mens vi reduserer gradene. Vi har nå gradene D = (0, 0, 0, 0, 1, 1).

Til slutt kobler vi sammen de to gjenværende toppunktene i grad 1, nemlig toppunktene i tall 5 og 6. Vi har faktisk rekonstruert det opprinnelige treet T.

Dekoding - andre metode

I stedet for en sekvens av grader fra hvert toppunkt, kan vi bruke en sekvens av hjørner som vi ennå ikke har behandlet. $D$ $Jeg$

Algoritme

Treet kan rekonstrueres ved hjelp av følgende inverse algoritme:

Données : suite de Prüfer P de longueur n – 2 Créer un graphe T composé de n sommets isolés numérotés de 1 à n Créer une suite I des numéros de 1 à n Tant qu'il reste des éléments dans P et plus de deux éléments dans I Soit s le premier élément de la suite P Identifier le plus petit élément j de I n'apparaissant pas dans la suite P Ajouter l'arête allant de j à s Enlever j de I et s de P Fin Tant que Ajouter l'arête reliant les deux sommets restant dans I

Eksempel

Tenk på følgende . Det må igjen tillate oss å rekonstruere treet i figuren ovenfor. $P = (4,4,4,5)$

I utgangspunktet var jeg = (1, 2, 3, 4, 5, 6). Deretter:

Det første elementet i P er 4 og den minste element av jeg ikke vises i P er 1. Kobles vertekser 1 og 4 i T og fjernes henholdsvis I og P . På dette punktet er I = (2, 3, 4, 5, 6) og P = (4, 4, 5).
Det første elementet i P er 4 og den minste element av jeg ikke vises i P er 2. forbinder punktene 2 og 4 i T og fjernes henholdsvis I og P . På dette punktet er I = (3, 4, 5, 6) og P = (4, 5).
Det første elementet i P er 4 og den minste element av jeg ikke vises i P er 3. Den forbinder punktene 3 og 4 i T og fjernes henholdsvis I og P . På dette punktet er jeg = (4, 5, 6) og P = (5).
Den eneste element av P er 5 og den minste element av jeg ikke vises i P er 4. Den forbinder toppene 4 og 5 i T og fjernes henholdsvis fra I og P . På dette punktet er I = (5, 6) og P er tom.

Til slutt kobler vi de gjenværende toppunktene 5 og 6. Vi har rekonstruert det opprinnelige treet T.

Demonstrasjon av Cayleys formel

I kombinatorisk vitenskap sier Cayleys formel at antallet "dekorerte" (nummererte) trær med n hjørner er . Figuren motsatt gjør det mulig å se at det faktisk finnes og tydelige dekorerte trær med henholdsvis 2, 3 eller 4 hjørner. $n ^ {{n-2}}$ $2 ^ {0}$ $3 ^ {1}$ $4 ^ {2}$

Prinsippet for demonstrasjonen

Vi viser først at:

for et tre T eksisterer det bare en Prüfer-sekvens P som beskriver T ;
for en gitt sekvens P med lengde n - 2, er det en enkelt graf T nummerert fra 1 til n hvis Prüfer-sekvens er P , og det er et tre.

Prüfer-kodingen gir derfor en sammenheng mellom settet av trær nummerert med n hjørner og settet med sekvenser med lengden n - 2 sammensatt av verdier i intervallet [1, n ]. Ettersom sistnevnte har elementer, og siden Prüfer-koding er bijektiv, demonstrerer dette Cayleys formel. $n ^ {{n-2}}$

Utvidelse

Vi kan gå lenger og bevise at antall trær som dekker en fullstendig graf over grader er lik den multinomiale koeffisienten . $K_n$ ${\ displaystyle d_ {1}, d_ {2}, \ dots, d_ {n}}$ ${\ frac {(n-2)!} {(d _ {{1}} - 1)! (d _ {{2}} - 1)! \ cdots (d _ {{n}} - 1)! }}$

Beviset er basert på det faktum at tallet i Prüfer-oppfølgeren vises nøyaktig ganger. $Jeg$ ${\ displaystyle d_ {i} -1}$

Merknader og referanser

Prüfer-koding på Apprendre en ligne.net, Didier Müller, 10. februar 2003
(de) Prüfer, H., “ Neuer Beweis eines Satzes über Permutationen ” , Arch. Matte. Phys. , vol. 27,1918, s. 742–744
(in) Jens Gottlieb, Bryant A. Julstrom Günther R. Raidl, and Franz Rothlauf ,. " Prüfer numbers: A poor representation of evolutionary search for spanning trees " , Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001) , 2001, s. 343–350 ( les online )

Tilleggsbibliografi

(en) Vadim Lozin , "Fra ord til grafer og tilbake" , i C. Martín-Vide, A. Okhotin og D. Shapira (redaktører), språk og automatteori og applikasjoner. LATA 2019 , Springer Cham, koll. "Forelesningsnotater i Computer Science" ( n o 11417)2019( ISBN 978-3-030-13434-1 , DOI 10.1007 / 978-3-030-13435-8_3 ) , s. 43–54.