Arbre (combinatoire)

Pour les articles homonymes, voir Arbre (homonymie).

Un arbre possède des propriété structurelles, par exemple enraciné ou non-enraciné, plans ou non-plans, labellisé ou non-labellisé. En combinatoire, on compte le nombre de tels arbres possédant un nombre fixe n de nœuds en fonction de leur classe.

Sommaire

1 Arbre planaire
- 1.1 Arbre planaire enraciné
- 1.2 Arbre planaire étiqueté
2 Arbre non-planaire
- 2.1 Arbre étiqueté (arbre couvrant)
3 Annexes
- 3.1 Liens internes
- 3.2 Notes et références

Arbre planaire

Deux arbres planaires différents.

Un arbre planaire est un graphe orienté acyclique représenté dans un plan (par un plongement) sans que les arêtes se croisent. Ces arbres sont également appelés arbres ordonnés notamment dans le cas des arbres enracinés. C'est-à-dire que, pour chaque nœud de l'arbre, les nœuds adjacents (ou fils) sont ordonnés ; on peut ainsi parler du j-ième fils d'un nœud.

Compter le nombre d'arbres planaires revient à compter le nombre de plongements possibles dans le plan.

Arbre planaire enraciné

Les 5 arbres de Catalan (arbres planaires enracinés) de 4 nœuds. en rouge : la racine, en vert : le nœud fantôme.

Les arbres planaires enracinés sont également appelés arbres de Catalan. Ce sont des arbres arbres enracinés et planaires : ils possèdent une unique racine et chaque nœud engendre un ensemble ordonné de fils.

Éventuellement, la racine de l'arbre peut être jointe à un nœud fictif, ce qui justifie le terme enraciné. Dans ce cas, tous les nœuds $v$ (y compris la racine) ont un degré qui vérifie : $\scriptstyle d(v)=d^+(v)+1$ où $\scriptstyle d^+(v)$ est le nombre de fils de $v$ .

Le nombre d'arbres planaires enracinés avec n≥1 nœuds est donné par le (n-1)-ième nombre de Catalan (d'où le nom de l'arbre) :

$C_{n-1}=\frac{1}{n}{2n-2 \choose n-1}$ .

Un cas particulier d'arbre planaire enraciné est le cas des arbres binaires. Les nœuds d'un arbre binaire possèdent soit 2 fils (ils sont alors appelés nœuds internes), ou aucun fils (ce sont alors des feuilles). Dans un arbre binaire, il y a k nœuds internes pour k+1 feuilles. Le nombre d'arbres binaires possédant k nœuds internes (c'est-à-dire n=2k+1 nœuds) est donné par le k-ième nombre de Catalan : $\scriptstyle C_k=\frac{1}{k+1}{2k \choose k}$ .

Plus généralement, on peut considérer les arbres m-aires (planaires et enracinés) dont chaque nœud possède m fils. Le nombre de tels arbres possédant k nœuds internes est donné par : $\scriptstyle \frac{1}{(m-1)k+1}{mk \choose k}$ .

Arbre planaire étiqueté

Les 20 arbres planaires enracinés étiquetés de 4 nœuds

Les arbres planaires étiquetés sont des arbres enracinés et étiquetés : chacun des n nœuds de l'arbre est numéroté de 1 à n (appelée étiquette) et engendre un ensemble ordonné de fils.

Le nombre d'arbres planaires étiqueté à n nœuds est donné par $\frac{(2n-3)!}{(n-1)!}$ .

Arbre planaire étiqueté et enraciné

Le nombre d'arbres à n nœuds, planaires étiquetés et enracinés est donné par : $\scriptstyle \frac{n(2n-3)!}{(n-1)!}$ puisque chacun des n nœuds peut être la racine de l'arbre planaire étiqueté.

Arbre non-planaire

Au contraire des arbres planaires, l'ensemble des fils des nœuds d'un arbre (non-planaires) ne possède pas de structure d'ordre. Ces arbres sont appelés arbres de Pólya.

Il n'existe pas de formule récursive directe pour compter les arbres enracinés et non-enracinés (non-planaires et non-étiquetés). On utilise alors les fonctions génératrices et la combinatoire de Pólya, d'où le nom des arbres. On note $\scriptstyle t_n$ le nombre d'arbres enracinés à n nœuds et $\scriptstyle \tilde{t}_n$ le nombre d'arbres non-enracinés à n nœuds. Leurs premières valeurs sont :

		n=1	n=2	n=3	n=4	...
$\displaystyle t_n =$		1	1	2	4	...
$\tilde{t}_n =$		1	1	1	2	...

$\displaystyle t_1 = 1 ,$ $\displaystyle t_2 = 1 ,$ $\displaystyle t_3 = 2 ,$ $\displaystyle t_4 = 4 ,$

$\tilde{t}_1 = 1 ,$ $\tilde{t}_2 = 1 ,$ $\tilde{t}_3 = 1 ,$ $\tilde{t}_4 = 2 ,$

Les fonctions génératrices correspondantes sont définies par :

$t(x) = \sum_{n\ge 1} t_n x^n \;\;\;\; \hbox{et} \;\;\;\; \tilde{t}(x) = \sum_{n\ge 1} \tilde{t}_n x^n$ .

Ces fonctions vérifient les formules suivantes :

$t(x) = x\exp\left(t(x) + \frac{1}{2}t(x^2) + \frac{1}{3}t(x^3) + ...\right)$ ,

$\tilde{t}(x) = t(x) - \frac{1}{2}t(x)^2 + \frac{1}{2}t(x^2)$ .

Arbre étiqueté (arbre couvrant)

Les 16 arbres étiquetés (non planaires) à 4 nœuds.

Les arbres étiquetés (non-planaires) sont parfois appelés arbres de Cayley. Chaque nœud d'un arbre à n nœuds est labellisé par une étiquette allant de 1 à n. De tels arbres peuvent être interprétés comme les arbres couvrants d'un graphe complet à n nœuds. Le nombre de tels arbres est donné par la formule de Cayley : $n n - 2$ .

Arbre étiqueté et enraciné
Le nombre d'arbres à n nœuds, étiquetés et enracinés est $n n - 1$ puisque chacun des n nœuds peut-être la racine de l'arbre étiqueté.

Annexes

Liens internes

Notes et références

(en) M. Drmota, Random trees - An Interplay between Combinatorics and Probability, Springer Verlag/Wien New York (2009), ISBN 978-3-211-75355-2

Portail de l'informatique théorique

Catégorie :

Probabilités

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Arbre (combinatoire) de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

COMBINATOIRE (ANALYSE) — L’analyse combinatoire est l’ensemble des techniques qui servent, en mathématiques, à compter (ou dénombrer ) certaines structures finies , ou à les énumérer (établir des listes exhaustives de structures considérées), enfin à démontrer leur… … Encyclopédie Universelle
Arbre De Steiner — Pour les articles homonymes, voir Steiner. Solution pour trois points. Le point de Steiner est au centre des trois autres points (il n y a pas de connexion directe entre A … Wikipédia en Français
Arbre de steiner — Pour les articles homonymes, voir Steiner. Solution pour trois points. Le point de Steiner est au centre des trois autres points (il n y a pas de connexion directe entre A … Wikipédia en Français
Arbre (homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « arbre », sur le Wiktionnaire (dictionnaire universel) Au sens premier, le mot arbre, désigne en… … Wikipédia en Français
Arbre de Steiner — Pour les articles homonymes, voir Steiner. Solution pour trois points. Le point de Steiner est au centre des trois autres points (il n y a pas de connexion directe entre A, B et C) … Wikipédia en Français
Explosion Combinatoire — Pour les articles homonymes, voir combinatoire (homonymie). On nomme explosion combinatoire en recherche opérationnelle, et en particulier dans le domaine de la programmation dynamique, le fait qu un petit changement du nombre de données à… … Wikipédia en Français
Décomposition-arbre — Décomposition arborescente En théorie des graphes, la décomposition arborescente (en anglais : tree decomposition) consiste en la décomposition d un graphe en séparateurs connectés dans un arbre. Cette méthode a été proposée par Seymour et… … Wikipédia en Français
Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… … Wikipédia en Français
Graphe (mathématiques) — Théorie des graphes Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… … Wikipédia en Français
Graphe (théorie des graphes) — Théorie des graphes Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Arbre (combinatoire)

Sommaire