n^{n−2}

PAR

PIERRE DUCHET

0. INTRODUCTION.

La formule de Cayley [3] qui évalue le nombre d’arbres étiquetés à n sommets reçut en 1918 une jolie démonstration bijective due à Prüfer [11], qui fournit un codage canonique de ces arbres dans l’ensemble produit [n]^{n−2}, où [n] := {1, …, n}. Une généralisation de ces résultats est ici proposée: Cayley et Prüfer énuméraient les arbres qui assurent la connexion des éléments d’un unique ensemble; on obtient ici le codage et l’ énumération des arbres sur [n] qui assurent la connexion des éléments de chaque membre d’une famille quelconque X_{1}, X_{2}, …, X_{m} de parties de [n].

Dans tout l’article, X désignera l’ensemble générique à n éléments. Un hypergraphe sur X est un couple H = (X, F) où F est une famille de parties de X (cf. [2] et [9]). Les ensembles de F sont les arêtes de H; les éléments de X sont les sommets de H et n est l’ordre de H. D’autres notions indispensables seront introduite au moment de leur utilisation.

Evidemment, le problème considéré n’a d’intérêt que pour les hypergraphes qui admettent au moins un arbre solution. Connus sous le nom d’hypergraphes arborés, ces hypergraphes ont été caractérisées de diverses manières [4,8,12]. Voir [2,5,6] pour une approche synthétique de ces structures.

(0.1) Definition. On note Π(X) l’ensemble des arbres dont les sommets sont les éléments de X. Un arbre T ∈ Π(X) est un arbre de base pour un hypergraphe H = (X, (X_{i})_{i∈I}) si chaque X_{i} induit un sous arbre de T. On note Π(H) l’ensemble des arbres de base de H. L’hypergraphe H est arborée dès que Π(H) est non vide.

1. CAS D’UNE PARTITION: SOUS-ARBRES PRESCRITS.

Soit M = {X_{1}, …, X_{m}} une partition de X. Par commodité on identifiera M à l’hypergraphe (X, M). Tout arbre de Π(M) peut être construit en choisissant d’abord pour chaque i, 1 ≤ i ≤ m, un arbre T_{i} ∈ Π(X_{i}), puis en complétant la forêt obtenue. Notons Π(X; T_{1}, T_{2}, …, T_{m}) l’ensemble des arbres de Π(X) qui contiennent chaque T_{i}.

(1.1) Proposition. (Moon [10]). |Π(X; T_{1}, T_{2}, …, T_{m})| = |X_{1}| ⋯ |X_{m}| · |X|^{m−2}. □

Ainsi la cardinalité de Π(X; T_{1}, T_{2}, …, T_{m}) ne dépend que de la partition M. En notant Π_{M} l’ensemble X_{1} × ⋯ × X_{m} × X^{m−2}, on a:

(1.2) Corollaire. Pour toute partition M = (X_{i})_{i∈I} de X, on a:

Π(M) ≃ Π_{M} × ∏_{i∈I} Π(X_{i}). □

Nous allons en fait redémontrer la formule de Moon en exhibant une bijection canonique entre les ensembles Π(X; T_{1}, T_{2}, …, T_{m}) et X_{1} × ⋯ × X_{m} × X^{m−2}, dont la construction s’inspire du codage de Prüfer.

Soit T ∈ Π(X; T_{1}, T_{2}, …, T_{m}); en contractant chaque T_{i} en un sommet unique, l’arbre T devient un arbre à m sommets que l’on peut identifier à un arbre T_{∗} sur {1, …, m}. Définissons une séquence d’entiers r(1), …, r(m) et une séquence p(1), …, p(m) d’éléments de X de la maniére suivante:

(1.3) \{ \begin{matrix}r(1) est le plus petit sommet pedant de l’arbre T_{∗}; \\ r(i + 1) est le plus petit sommet pendant de l’arbre T_{∗}\\{r(l), …, r(i)\}; \end{matrix}

(1.4) \{ \begin{matrix}p(i) est l’unique sommet du sous-arbre T \(X_{r(1)} ∪ ⋯ ∪ X_{r(i)}) qui est \\ adjacent (dans T) à l’ensemble X_{r(i)}, ceci pour chaque i ∈ \{1, …, m\}. \end{matrix}

Remarquons que p(m − 1) ∈ X_{m} et que r est une permutation de [m] qui laisse m invariant. Définissons une autre séquence d’éléments de X, soit p_{1}, …, p_{m} par les conditions suivantes:

(1.4)  \{ \begin{matrix}Pour 1 ≤ i ≤ m − 1, \{p_{r(i)}, p(i)\} est la seule arête de T \\ qui sorte del’ensemble X_{r(i)}; \\ p_{m} := p(m − 1). \end{matrix}

(1.5) Theorème et définition. Soit M = (X_{1}, …, X_{m}) une partition de X, et pour 1 ≤ i ≤ m soit T_{i} un arbre sur X_{i}. L’applicaton p_{∗} qui à chaque arbre T de Π(X; T_{1}, …, T_{m}) associe son code de Prüfer généralisé, défini par:

p_{∗}(T) = (p_{1}, p_{2}, …, p_{m}, p(1), p(2), …, p(m − 2))

est une bijection de Π(M) sur l’ensemble X_{1} × ⋯ × X_{m} × X^{m−2}.

Indication sur la démonstration: il suffit de vérifier que la suite r(i) est caractérisée par la propriété:

(1.6)  \{ \begin{matrix}r(i + 1) est le plus petit entier qui ne figure pas dans la suite \\ r(1), …, r(i), p(i + 1), …, p(m − 1), \end{matrix}

ce qui permet de construire p_{∗}^{−1}. On remarquera que la séquence des p(i), avec 1 ≤ i ≤ m − 2, est le code de Prüfer usuel correspondant à l’arbre T_{∗}. □

2. FAMILLES ARBOREES, CONVEXES ET LIENS.

Deux idées essentielles gouvernent l’étude de la structure des familles arborées. La première est la remarque que toute intersection de parties connexes d’un arbre est encore connexe; ainsi les parties qui induisent des sous-arbres constituent les fermés d’une “fermeture de Moore” ou d’une “convexité” au sens abstrait (cf. [7] pour ce point de vue). La seconde idée est que parmi ces “convexes”, certains jouent un rôle essentiel dans la connexion de la famille arbrée considérée. Les définitions suivantes sont relatives à un hypergraphe sur X, soit H = (X, (X_{i})_{i∈I}).

(2.1) Definition. Les parties de X de la forme ⋂_{i∈J} X_{i}, où J ⊆ I, sont appelés parties H-convexes. En particulier l’ensemble X est convexe. L’enveloppe convexe d’une partie A de X est l’intersection des convexes qui contiennent A; elle est notée [A]_{H}.

(2.2) Definition. La localisation de H sur une partie Y de X, notée H]Y [ est la famille des traces sur Y des ensembles de H qui ne contiennent pas Y. On appelle lien de H toute partie Y de X qui est H-convexe et telle que la localisation H]Y [ soit non-connexe; il est commode de considérer qu’un hypergraphe vide d’arêtes est nonconnexe; ainsi chaque singleton {x} ⊆ X est-il un lien, dit trivial. Les composantes connexes de H]Y [ forment ce qu’on appelle la partition (de liasion) de Y relative à H, notée Part_{H}(Y) ou simplement Part(Y).

EXEMPLES. Les arêtes d’un graphe G sont des liens de G (la partition de liaison associée à chaque arête est la bipartition triviale en singletons). Si G est connexe, il n’y a pas d’autres lien non trivial. Si G est non-connexe, son ensemble de sommet est aussi un lien. Si F est une partition de X, l’ensemble X lui-mem̂e est un lien de l’hypergraphe H = (X, F) et F est la partition de liaison correspondante; les autres liens non triviaux de H sont les ensembles de la partition F (les partitions de liaisons correspondantes étant les partitions triviales en singletons).

(2.3) Proposition. Tout lien non trivial L d’un hypergraphe H est l’enveloppe Hconvexe d’un ensemble de cardinal 2. □

(2.4) Proposition. Un hypergraphe arboré d’ordre n a au maximum n − 1 liens non triviaux. □

3. DETERMINATION DES ARBRES DE BASE.

La structure de liasion d’un hypergraphe H sur X est l’ensemble de ses liens, considéré comme hypergraphe sur X et muni de la relation d’ordre ⊆. Lorsque la structure de liasion est considérée comme hypergraphe, les liens triviaux ne jouent aucun rôle. Les propositions précédentes indiquent que la structure de liaison est plus simple (remarquablement plus simple, en général) que l’hypergraphe. Néanmoins, pour le problème qui nous interesse ici, l’étude de la structure de liaison suffit:

(3.1) Lemma fondamental. Soit L la structure de liaison d’un hypergraphe arboré H. On a: Π(L) = Π(H). □

(3.2) Théorème. Soit H un hypergraphe arboré sur X et soit L l’ensemble de ses liens. Il existe une bijection canonique de Π(H) sur l’ensemble produit

∏_{L∈L} Π_{P art(L)}.

(3.3) Corollaire. Soit (L_{i})_{1≤i≤m} la liste des liens de l’hypergraphe arboré H. Chaque lien L_{i} a l_{i} sommets, c(i) composantes connexes de cardinalités respectives c_{i,j}, 1 ≤ j ≤ c(i). Alors, les nombres d’arbres de base de H est donné par la formule:

|Π(H)| = ∏_{1≤i≤m} l_{i}^{c(i)−2} ∏_{1≤j≤c(i)} c_{i,j}.

Quelques indications sur la démonstration: en fait tout arbre de base d’un hypergraphe arboré H peut être construit par extensions successives, en choisissant de proche en proche un arbre sur chaque lien, obtenu par extension des arbres déjà contruits sur les liens plus petits. Il s’avère que les choix d’extensions possibles sont mutuellement indépendants (cela résulte notamment des résultats énoncés en annexe); comme chaque extension est un cas où s’applique le théorème (1.5), on aboutit au théorème (3.2) et à son corollaire. Pour plus de détails voir [6]. □

4. COMMENTAIRES ET APPLICATIONS.

(4.1) Il n’est pas très difficile de bâtir un algorithme qui, étant donné un hypergraphe arboré H à n sommets et m arêtes, détermine en temps O(mn^{3}) la structure de liaison et par là, l’ensemble des arbres de base. Le nombre d’arbre de base d’un hypergraphe arboré H est en général exponentiellement grand par rapport à m et n, il est donc clair que le comptage et la description complète de Π(H) ne peut se faire de manière rapide qu’en raison de la structure produit (de longueur polynomiale en n) de l’ensemble Π(H), énoncée par le théorème (3.2). A tout arbre de base peut être canoniquement associé un code “de Prüfer généralisé” dans l’ensemble produit

∏_{L∈L} Π_{P art(L)}.

Ce code s’obtient par concaténation des codages de Prüfer généralisés associés, selon le théorème (1.5), aux sous-arbres induits par les liens modulo les partitions de liaison correspondantes.

(4.2) Le concept de structure de liaison rend possible la solution d’un vieux problème (dû à Renz, cf. [6]) à savoir la caractérisation des hypergraphes de chemins d’arbre, c’est à dire des hypergraphes arborés admettant un arbre de base T qui induise un chemin sur chaque arête de H. Une telle caractérisation, de type “configurations exclues”, a récemment été obtenue par Arami et l’auteur [1], aussi bien dans le cas orienté que non orienté. La démonstration de ces caractérisations permet la reconnaissance de ces hypergraphes par un algorithme rapide, basé sur l’algorithme (4.1).

(4.3) Plus générallement, les méthodes développées ici devraient permettre une organisation mieux structurée des bases de données relationnelles existantes, puisque l’efficacité d’une telle organisation repose, en l’état actuel de la question, sur les hypergraphes arborés (ou leur duaux) et sur la construction d’arbres de base d’un type donné pour ces hypergraphes.

(4.4) Il est possible d’interpréter les nombres d’arbres de base d’un hypergraphe arboré comme les déterminants d’un certain type de matrices qui, pour des raisons non encore élucidées, interviennent également en Géométrie Algébrique (“M-matrices de graphes algébriques”). Il semble intéressant dans ce contexte de développer des généralisations matricielles du théorème (3.2), par analogie avec les résultats classiques sur l’énumération des arbres couvrants d’un graphe donné. Cela sera l’objet d’un travail ultérieur.

ANNEXE: LIENS ET PARTITTONS SPECTRALES.

Nous allons donner une autre description de la structure de liaison d’un hypergraphe arboré, utile du point de vue algorithmique. Dans toute cette section H désigne un hypergraphe sur X. Si σ est une partition quelconque de X, on note H/σ l’hypergraphe quotient obtenu par contraction de chaque ensemble constitutif de σ. Pour toute partition partielle τ ⊆ σ, on note τ̂ l’intersection de tous les ensembles H-convexes qui rencontre chaque ensemble de τ.

(A.1) Definition. Le spectre (d’ordre 1) d’un hypergraphe H sur X, noté sp(H) est l’hypergraphe sur X formé des liens non triviaux minimaux (pour l’inclusion). La séquence spectrale S_{1}, …, S_{s} de H est définie récursivement par:

(A.2)  \{ \begin{matrix}S_{1} := sp(H) \\ S_{k+1} := sp(H/σ_{k}) oú σ_{k} est la partition de X formée \\ des composantes connexes de S_{k}. \end{matrix}

Les σ_{k} sont appelées les partitions spectrales de H. L’entier s (la “hauteur” de H) est le premier indice tel que S_{s+1} ne contienne aucune arête. La démonstration purement technique du lemme suivant est laissé au soin du lecteur:

(A.3) Lemme. Si H est arboré, chaque spectre S_{k} (spectre de hauteur k) est une hyperforêt, c’est à dire un hypergraphe sans aucun cycle. L’application E ↦ Ê est une bijection entre l’ensemble des arêtes des spectres successifs de H et l’ensemble des liens non triviaux de H. Une arête de E de S_{k} est l’image du lien Ê par la surjection canonique X → X/σ_{k}; la partition σ_{k} correspond par cette surjection à la partition de liaison de Ê.

Une description des arbres de base de H et une démonstration du théorème (3.2) sont obtenus à partir du résultat suivant où σ_{0} désigne la partition triviale de X en singletons:

(A.4) Théorème. Si H est un hypergraphe arboré, les arbres de base pour H sont exactement les arbres T sur X tels que chaque quotient T/σ_{k−1} soit, pour 1 ≤ k ≤ s, un arbre de base de S_{k}.

References

[1] Z. Arami, P. Duchet, Systems of paths in a tree, en preparation.

[2] C. Berge, Hypergraphes, Gauthiers-Vilars, Paris, 1987.

[3] A. Cayley, A theorem on trees, Quart. J. Math. 23 (1889), 376–378.

[4] P. Duchet, Propriété de Helly et problèmes de représentation, Proc. Int. Coll. CNRS 260 (1978), CNRS, Paris, 117–118.

[5] P. Duchet, Classical Perfect Graphs, an introduction with emphasis on triangulated and interval graphs, Ann. Disc. Math. 21 (1984), 67–96.

[6] P. Duchet, Tree hypergraphs and their basic trees, Preprint, Univ. Paris 6, 1985.

[7] P. Duchet, La convexité dans les structures combinatoires, Actes du Sémin. Lotharingien, 12^{e} Session, Kleebach, 1985, pp. 67–107.

[8] C. Flament, Hypergraphes arborés, Discrete Math. 21 (1978), 223–226.

[9] L. Lovász, Combinatorial problems and exercises, North Holland Pub. Co., Amsterdam–New York–Oxford, 1979.

[10] J. W. Moon, Enumerating labelled trees, Graph Theory and Theoretical Physics (F. Harary, ed.), Acad. Press, London–New York, 1967, pp. 261–271.

[11] A. Prüfer, Archiv Math. Phys. 27 (1918), 142–144.

[12] P. J. Slater, A characterization of soft hypergraphs, Canad. Math. Bull. 21 (1978), 335–337.