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

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 multiset 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.

Arbres et classes

TBD X-arbre et représentation combinatoire des arbres par bi-partition. TBD c'est l'ET 2024-2025