Représentations en combinatoire : arbres, mots, chemins

Introduction

En combinatoire, la représentation d'ensembles ou de processus par des structures visuelles ou séquences est essentielle pour leur étude. Nous abordons ici trois types principaux de représentations : les arbres, les mots, et les chemins.

1. Représentation par des arbres

Un arbore est une structure hiérarchique non cyclique composée de nœuds reliés par des arêtes. Il permet de représenter des hiérarchies ou des processus de décision.

Exemple : arbre binaire

Un arbre binaire est un arbre dont chaque nœud possède au plus deux fils, appelés gauche et droit. La représentation est souvent utilisée pour les expressions arithmétiques ou pour la recherche dans une structure de données.

Visualisation

Les arbres se représentent souvent avec la racine en haut, les branches descendant vers les feuilles :

2. Représentation par des mots

Un mot est une séquence finie de lettres issues d’un alphabet \(A\).

Par exemple, si \(A = \{a, b, c\}\), un mot peut être : \(abacb\).

Résumé :

• Mot fini : une suite de lettres
• Représenté par la concaténation de lettres : \(u = a_1 a_2 ... a_n\)

Utilités

Les mots permettent de modéliser des automates, des codes ou des processus séquentiels.

3. Représentation par des chemins

Un chemin dans un graphe est une suite de sommets reliés par des arêtes. Il peut commencer et se terminer en différents sommets ou revenir au point de départ (cycle).

Exemple : chemin simple

Considérons un graphe avec les sommets \(A, B, C, D\), un chemin pourrait être : \(A ightarrow B ightarrow C ightarrow D\).

Notation

Un chemin peut s’écrire sous la forme : \( ext{Chemin} = (s_0, s_1, ..., s_k)\), où chaque paire \((s_i, s_{i+1})\) est une arête du graphe.

Conclusion

Ces représentations sont fondamentales en combinatoire pour analyser, compter ou visualiser des ensembles et des processus complexes. Leur maîtrise facilite la résolution de nombreux problèmes de dénombrement et d’algèbre combinatoire.