The reconstruction of a tree from its number deck

✍ Scribed by I Krasikov; J Schönheim

• Publisher: Elsevier Science
• Year: 1985
• Tongue: English
• Weight: 555 KB
• Volume: 53
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(85)90136-0

✦ Synopsis

Those trees are characterized which are reconstructible f~om the knowledge of the sizes of the connected components in each maximal subgraph.

II est connu que la conjecture de Ulam est vraie pour les arbres. Dam un language d~ Harary ceci s'exprime de la fa~n suivante:

Si les n for6ts, qu'on a obtenues en enlevant successivement chacun des sommets d'un arbre ~t n sommets, sont donn~es surn cartes, flops on est capable de reconstruire l'arbre.

On s'est demand6 quels sont les arbres qu'on peut reconstruire si stir les cartes envisag~es figurent seulement les cardinalit~s des arbres composant les for6ts.

Un tel paquet de cartes 6tant dit Paquet Num6dque, nous allons caract6riser (voir Th~or~me 3) les arbres qui sont reconstructibles 10rsque le Paquet Num6rique est donn6. La figure 1 montre qu'il y a des arbres qui ne jouissent pas de cette propri6t6. On y voit deux arbres qui ne sont pas isomorphes mats ont le m~me Paquet Num6dque.

La d6monstration du r~sultat est constructive, et conduit h un algorithme. Celui-ci foumit tom les arbres qui ont le m6me Paquet Num6dque.