Arbres
Explorer les propriétés et l'intérêt de l'arbre.
Définitions et propriétés
Représentation graphique
Problème de l'arbre couvrant
Arbres de Cayley
Arbres plantés
Arbres planaires
Arbres de Catalan
Arbres de Galton-Watson
Isomorphisme d'arbres
Montrez que tout automorphisme d'arbre laisse invariant au moins un sommet ou une arête.
solution
solution
TBD écrire propre
- vrai à 1 ou 2 sommets
- les feuilles sont envoyées sur les feuilles par automorphisme
- on supprime les feuilles
- la restriction de l'automorphisme est un automorphisme de l'arbre effeuillé et la récursion passe.
Arbres de Pólya
TBD def par par bijection d'arbres plantés TBD def ensembliste avec multi set : ensemble avec répétitions possibles (faire dessin) TBD def ensembliste se binarise en prenant juste des multi-set de taille 2.
isomorphisme Arbres planté :
- Aho, Hopcroft and Ullman https://hal.science/hal-04232137/document
- https://info.faidherbe.org/MPII/11.pdf
Arbres non plantés
TBD https://perso.ens-lyon.fr/eric.thierry/Graphes2010/marthe-bonamy.pdf on peut le faire de façon linéaire.