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
Dit binaires
On connaît l'ordre gauche ou droite des enfants.
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 multiset 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.
Arbres et classes
TBD X-arbre et représentation combinatoire des arbres par bi-partition. TBD c'est l'ET 2024-2025