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

TBD écrire propre

  1. vrai à 1 ou 2 sommets
  2. les feuilles sont envoyées sur les feuilles par automorphisme
  3. on supprime les feuilles
  4. 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é :

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.