Codifica Prüfer

In matematica , la codifica di Prüfer è un metodo per descrivere in modo compatto un albero con vertici numerati. Questa codifica rappresenta un albero di n vertici numerati con una sequenza di n-2 termini. Una data sequenza P corrisponde a uno e un solo albero numerato da 1 a n . $P = (x_ {1}, x_ {2}, x_ {3}, ..., x _ {{n-2}})$

Le sequenze di Prüfer furono usate per la prima volta da Heinz Prüfer per dimostrare la formula di Cayley nel 1918. Possono anche essere usate nella programmazione di computer per registrare la struttura di un albero in modo più compatto rispetto ai puntatori .

Codifica

Nota: tutti gli esempi che seguono fanno riferimento all'albero T qui accanto.

Algoritmo

La sequenza di Prüfer è costruita utilizzando il seguente algoritmo :

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

Esempio

Considera l'albero nella figura sopra.

All'inizio, 1 è il foglio di numero minimo , è quindi quello che si ritira per primo e si mette 4 (il numero del ramo a cui era collegato) nel seguito di Prüfer.

I vertici 2 e 3 sono i successivi da rimuovere e aggiungiamo altre due volte 4 dopo Prüfer.

Il vertice 4 è ora una foglia e ha il numero più basso, quindi lo rimuoviamo e aggiungiamo 5 (il ramo a cui era attaccato) alla fine della suite.

Sono rimasti solo due vertici, quindi ci fermiamo. La sequenza di Prüfer che codifica l'albero è . $P = (4,4,4,5)$

Decodifica - Primo metodo

Questo algoritmo si basa su una sequenza dei gradi di ogni vertice dell'albero . $D$ $T$

Algoritmo

L'albero può essere ricostruito utilizzando il seguente algoritmo inverso:

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

Esempio

Considera quanto segue . Deve permetterci di ricostruire l'albero nella figura sopra. $P = (4,4,4,5)$

In una prima fase creiamo un grafo con sei vertici isolati numerati da 1 a 6. Assegniamo a tutti un grado di default uguale a 1. Quindi, attraversiamo P aumentando il grado dei vertici che vi compaiono: aumentiamo tre volte il grado del vertice 4 e una volta il grado del vertice 5. Infine, abbiamo i gradi D = (1, 1, 1, 4, 2, 1).

Nella fase successiva, passiamo di nuovo a P:

Per x 1 = 4, cerchiamo il vertice con il numero di gradi più basso uguale a 1. È il numero di vertici 1 e colleghiamo i vertici 1 e 4, diminuendone i gradi. Ora abbiamo i gradi D = (0, 1, 1, 3, 2, 1).
Per x 2 = 4, cerchiamo il vertice con il numero di gradi più basso uguale a 1. È il numero di vertici 2 e colleghiamo i vertici 2 e 4, diminuendone i gradi. Ora abbiamo i gradi D = (0, 0, 1, 2, 2, 1).
Per x 3 = 4, cerchiamo il vertice con il numero di gradi più basso uguale a 1. È il numero di vertici 3 e colleghiamo i vertici 3 e 4, diminuendone i gradi. Ora abbiamo i gradi D = (0, 0, 0, 1, 2, 1).
Per x 4 = 5, cerchiamo il vertice con il numero di gradi più basso uguale a 1. È il numero di vertici 4 e colleghiamo i vertici 4 e 5, diminuendone i gradi. Ora abbiamo i gradi D = (0, 0, 0, 0, 1, 1).

Infine, colleghiamo i due vertici rimanenti di grado 1, ovvero i vertici dei numeri 5 e 6. Abbiamo infatti ricostruito l'albero originale T.

Decodifica - secondo metodo

Invece di una sequenza di gradi da ogni vertice, possiamo usare una sequenza di vertici che non abbiamo ancora elaborato. $D$ $io$

Algoritmo

L'albero può essere ricostruito utilizzando il seguente algoritmo inverso:

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

Esempio

Considera quanto segue . Deve ancora permetterci di ricostruire l'albero nella figura sopra. $P = (4,4,4,5)$

Inizialmente, I = (1, 2, 3, 4, 5, 6). Poi:

Il primo elemento di P è 4 e l'elemento più piccolo che non appaiono in P è 1. connects vertici 1 e 4 T e rimosso rispettivamente I e P . A questo punto, I = (2, 3, 4, 5, 6) e P = (4, 4, 5).
Il primo elemento di P è 4 e l'elemento più piccolo che non appaiono in P è 2. collega i vertici 2 e 4 a T e rimosso rispettivamente I e P . A questo punto, I = (3, 4, 5, 6) e P = (4, 5).
Il primo elemento di P è 4 e l'elemento più piccolo che non appaiono in P è 3. Si connette i vertici 3 e 4 in T e rimosso rispettivamente I e P . A questo punto, I = (4, 5, 6) e P = (5).
L'unico elemento di P è 5 e l'elemento più piccolo che non appaiono in P è 4. collega i picchi 4 e 5 in T e rimosso rispettivamente I e P . A questo punto, I = (5, 6) e P è vuoto.

Infine, colleghiamo i rimanenti vertici 5 e 6. Abbiamo ricostituito l'albero originale T.

Dimostrazione della formula di Cayley

Nella scienza combinatoria , la formula di Cayley afferma che il numero di alberi "decorati" (numerati) con n vertici è . Rende la figura opposto possibile vedere che ci sono effettivamente , e alberi decorati distinte con 2, 3 o 4 vertici rispettivamente. $n ^ {{n-2}}$ $2 ^ {0}$ $3 ^ {1}$ $4 ^ {2}$

Principio della dimostrazione

Per prima cosa dimostriamo che:

per un albero T , esiste solo una sequenza di Prüfer P che descrive T ;
per una data sequenza P di lunghezza n - 2, v'è un unico grafico T numerate da 1 a n cui sequenza è Prüfer P , ed è un albero.

La codifica di Prüfer fornisce quindi una biiezione tra l'insieme di alberi numerati con n vertici e l'insieme di sequenze di lunghezza n - 2 composto da valori nell'intervallo [1, n ]. Poiché quest'ultimo ha elementi, e poiché la codifica di Prüfer è biiettiva, ciò dimostra la formula di Cayley. $n ^ {{n-2}}$

Estensione

Possiamo andare oltre e dimostrare che il numero di alberi che coprono un grafico completo di gradi è uguale al coefficiente multinomiale . $K_n$ ${\ displaystyle d_ {1}, d_ {2}, \ dots, d_ {n}}$ ${\ frac {(n-2)!} {(d _ {{1}} - 1)! (d _ {{2}} - 1)! \ cdots (d _ {{n}} - 1)! }}$

La prova si basa sul fatto che, nel seguito di Prüfer, il numero appare esattamente volte. $io$ ${\ displaystyle d_ {i} -1}$

Note e riferimenti

Prüfer codifica su Apprendre en ligne.net, Didier Müller, 10 Febbraio 2003
(de) Prüfer, H., " Neuer Beweis eines Satzes über Permutationen " , Arch. Matematica. Phys. , vol. 27,1918, p. 742–744
(in) Jens Gottlieb, Bryant A. Julstrom Günther R. Raidl e 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, p. 343-350 ( leggi in linea )

Bibliografia aggiuntiva

(it) Vadim Lozin , "Dalle parole ai grafici e ritorno" , in C. Martín-Vide, A. Okhotin e D. Shapira (editori), Teoria e applicazioni del linguaggio e degli automi. LATA 2019 , Springer Cham, coll. "Lecture Notes in Computer Science" ( n o 11417),2019( ISBN 978-3-030-13434-1 , DOI 10.1007 / 978-3-030-13435-8_3 ) , p. 43–54.