<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\input amstex
\input amsppt.sty

\magnification1200
\hsize13cm
\vsize19cm

\TagsOnLeft
\NoBlackBoxes


\def\si{\sigma}

\vskip1cm
\head {$n ^{n-2}$}\endhead
\vskip0,5cm
\centerline{\eightpoint PAR}
\vskip1cm
\centerline{\smc PIERRE DUCHET}
\vskip1cm




\document

\subhead {\bf 0.~INTRODUCTION} \endsubhead

\vskip.5cm

La formule de Cayley \cite {3} qui 
\'evalue le nombre d'arbres \'etiquet\'es \`a $n$ sommets
re\c cut en 1918 une jolie d\'emonstration bijective due \`a
Pr\"ufer \cite {11}, qui fournit un codage canonique de ces arbres
dans l'ensemble produit $[n]^{n-2}$, o\`u
$[n]:=\{1,\dots,n\}$. Une g\'en\'eralisation de
ces r\'esultats est ici propos\'ee: Cayley et
Pr\"ufer \'enum\'eraient les arbres qui assurent
la connexion des \'el\'ements d'un unique
ensemble; on obtient ici le codage et l' \'enum\'eration des arbres sur $[n]$ qui assurent la connexion des
\'el\'ements de chaque membre d'une famille quelconque $X_1,
X_2,\dots,X_m$ de parties de $[n]$.

Dans tout l'article, $X$ d\'esignera l'ensemble g\'en\'erique \`a n
\'el\'ements. Un {\it hypergraphe sur} $X$ est un couple
$\Cal H=(X,{\Cal F})$ o\`u ${\Cal F}$ est une famille de parties de
$X$ (cf. \cite {2} et \cite {9}). Les ensembles de $\Cal F$ sont les
{\it ar\^etes} de $\Cal H$; les \'el\'ements de $X$ sont les {\it
sommets} de $\Cal H$ et $n$ est l'{\it ordre} de $\Cal H$. D'autres
notions indispensables seront introduite au moment de leur
utilisation.

Evidemment, le probl\`eme consid\'er\'e n'a d'int\'er\^et que pour les
hypergraphes qui admettent au moins un arbre solution. Connus sous le 
nom d'{\it hypergraphes arbor\'es}, ces hypergraphes ont \'et\'e
caract\'eris\'ees de diverses mani\`eres \cite{4,8,12}. Voir \cite
{2,5,6} pour une approche synth\'etique de ces structures. 


\definition{(0.1) Definition}
On note $\Pi(X)$ l'ensemble des arbres dont les sommets sont les
\'el\'ements de $X$. Un arbre $T\in\Pi(X)$ est un {\it arbre de base}
pour un hypergraphe $\Cal H=(X,(X_i)_{i\in I})$ si chaque $X_i$ induit
un sous arbre de $T$. On note $\Pi(\Cal H)$ l'ensemble des arbres de
base de $\Cal H$. L'hypergraphe $\Cal H$ est {\it arbor\'ee}
d\graveaccent es que
$\Pi(\Cal H)$ est non vide. 
\enddefinition

\vskip.5cm
\subhead 1. CAS D'UNE PARTITION: SOUS-ARBRES PRESCRITS\endsubhead
\vskip.5cm

Soit $\Cal M=\{X_1,\dots,X_m\}$ une partition de $X$. Par commodit\'e
on identifiera $\Cal M$ \graveaccent a l'hypergraphe $(X,\Cal M)$. Tout
arbre de $\Pi(\Cal M)$ peut \^etre construit en choisissant d'abord pour
chaque $i$, $1\leq i\leq m$, un arbre $T_i\in\Pi(X_i)$, puis en
compl\'etant la for\^et obtenue. Notons $\Pi(X;T_1, T_2,\dots,T_m)$
l'ensemble des arbres de $\Pi(X)$ qui contiennent chaque $T_i$. 


\proclaim{(1.1) Proposition}{\rm(}Moon \cite{10}{\rm)}.
$|\Pi(X;T_1,T_2,\dots,T_m)|=|X_1|\cdots|X_m|\cdot|X|^{m-2}$.\quad \quad \qed
\endproclaim

Ainsi la cardinalit\'e de $\Pi(X;T_1,T_2,\dots,T_m)$ ne d\'epend que
de la partition $\Cal M$. En notant $\Pi_{\Cal M}$ l'ensemble
$X_1\times\dots\times X_m\times X^{m-2}$, on a:


\proclaim{(1.2) Corollaire}Pour toute partition $\Cal M=(X_i)_{i\in I}$ de
$X$, on a:
$$
\kern4.2cm   \Pi(\Cal M)\simeq\Pi_{\Cal M}\times\prod_{i\in I}\Pi(X_i).
\kern4.2cm \qed
$$
\endproclaim

Nous allons en fait red\'emontrer la formule de Moon en exhibant une
bijection canonique entre les ensembles $\Pi(X;T_1,T_2,\dots,T_m)$ et
$X_1\times\dots\times X_m\times X^{m-2}$, dont la construction
s'inspire du codage de Pr\"ufer. 

Soit $T\in\Pi(X;T_1,T_2,\dots,T_m)$; en contractant chaque $T_i$ en un
sommet unique, l'arbre $T$ devient un arbre \graveaccent a $m$ sommets
que l'on peut identifier \graveaccent a un arbre $T_*$ sur
$\{1,\dots,m\}$. D\'efinissons une s\'equence d'entiers
$r(1),\dots,r(m)$ et une s\'equence $p(1),\dots,p(m)$ d'\'el\'ements
de $X$ de la mani\'ere suivante:
$$\left\{ \matrix\format\l\\ 
r(1)\ \text{est le plus petit sommet pedant de l'arbre}\ T_*;\\
r(i+1)\ \text{est le plus petit sommet pendant de l'arbre}\ T_*\backslash\{r(l),\dots,r(i)\};
\endmatrix\right . \tag 1.3$$
$$\left\{ \matrix\format\l\\
p(i)\ \text{est l'unique sommet du sous-arbre}\
T\backslash(X_{r(1)}\cup\dots\cup X_{r(i)})\ \text{qui est} \\
\text {\quad adjacent (dans $T$) \graveaccent a l'ensemble}\ X_{r(i)},\ \text
{ceci pour chaque} \ i\in\{1,\dots,m\}.
\endmatrix\right. \tag 1.4$$

Remarquons que $p(m-1)\in X_m$ et que $r$ est une permutation de $[m]$
qui laisse $m$ invariant. D\'efinissons une autre s\'equence
d'\'el\'ements de $X$, soit $p_1,\dots,p_m$ par les conditions
suivantes:
$$\left\{ \matrix\format\l\\
\text{Pour}\ 1\leq i\leq m-1,\{p_{r(i)}, p(i)\}\ \text{est la seule
ar\^ete de} \ T\\ \text{\quad \quad qui sorte del'ensemble}\ X_{r(i)};\\
p_m:=p(m-1).
\endmatrix\right. \tag 1.4$$


\proclaim{(1.5) Theor\`eme et d\'efinition} Soit $\Cal M=(X_1,\dots,X_m)$
une partition de $X$, et pour $1\leq i\leq m$ soit $T_i$ un arbre sur
$X_i$. L'applicaton $p_*$ qui \graveaccent a chaque arbre $T$ de
$\Pi(X;T_1,\dots,T_m)$ associe son code de Pr\"ufer g\'en\'eralis\'e,
d\'efini par:
$$
p_*(T) = (p_1,p_2,\dots,p_m,p(1),p(2),\dots,p(m-2))
$$
est une bijection de $\Pi(\Cal M)$ sur l'ensemble
$X_1\times\dots\times X_m\times X ^{m-2}$.
\endproclaim

{\it Indication sur la d\'emonstration:} il suffit de v\'erifier que la
suite $r(i)$ est caract\'eris\'ee par la propri\'et\'e:
$$\left\{ \matrix\format\l\\
r(i+1)\ \text {est le plus petit entier qui ne figure pas dans la
suite}\\
r(1),\dots,r(i),p(i+1),\dots,p(m-1),
\endmatrix\right. \tag 1.6$$
ce qui permet de construire $p_*^{-1}$. On remarquera que la
s\'equence des $p(i)$, avec $1\leq i\leq m-2$, est le code de Pr\"ufer
usuel correspondant \graveaccent a l'arbre $T_*$.\quad \quad \qed

\vskip.5cm
\subhead 2. FAMILLES ARBOREES, CONVEXES ET LIENS\endsubhead
\vskip.5cm


Deux id\'ees essentielles gouvernent l'\'etude de la structure des
familles arbor\'ees. La premi\`ere 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\'es
d'une ``fermeture de Moore" ou d'une ``convexit\'e" au sens abstrait
(cf\. \cite{7} pour ce point de vue). La seconde id\'ee est que parmi
ces ``convexes", certains jouent un r\^ole essentiel dans la connexion de
la famille arbr\'ee consid\'er\'ee. Les d\'efinitions suivantes sont
relatives \graveaccent a un hypergraphe sur $X$, soit
$\Cal H=(X,(X_i)_{i\in I})$.


\definition{(2.1) Definition} 
Les parties de $X$ de la forme $\bigcap _{i \in J} ^{} X_i$, o\graveaccent u
$J\subseteq I$, sont appel\'es parties $\Cal H${\it-convexes}. En
particulier l'ensemble $X$ est convexe. L'{\it enveloppe convexe}
d'une partie $A$ de $X$ est l'intersection des convexes qui
contiennent $A$; elle est not\'ee $[A]_\Cal H$. 
\enddefinition


\definition {(2.2) Definition} 
La {\it localisation} de $\Cal H$ sur une partie $Y$ de $X$, not\'ee
$\Cal H \rbrack Y \lbrack$ est la famille des traces sur $Y$ des
ensembles de $\Cal H$ qui ne contiennent pas $Y$. On appelle {\it lien
de} $\Cal H$ toute partie $Y$ de $X$ qui est $\Cal H$-convexe et telle que la
localisation $\Cal H]Y[$ soit non-connexe; il est commode de consid\'erer qu'un 
hypergraphe vide d'ar\^etes est non-connexe; ainsi chaque singleton $\{x\}\subseteq X$ 
est-il un lien, dit {\it trivial}. Les composantes connexes de $\Cal H]Y[$ forment ce
qu'on appelle la {\it partition (de liasion)} de $Y$ relative
\graveaccent a $\Cal H$, not\'ee $\text {Part}_\Cal H(Y)$ ou
simplement $\text {Part}(Y)$.
\enddefinition


\example{EXEMPLES}  Les ar\^etes d'un graphe $G$ sont des liens de $G$ (la
partition de liaison associ\'ee \graveaccent a chaque ar\^ete 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 $\Cal F$ est une partition de $X$,
l'ensemble $X$ lui-me\^me est un lien de l'hypergraphe $\Cal H=(X, \Cal F)$
et $\Cal F$ est la partition de liaison correspondante; les autres
liens non triviaux de $\Cal H$ sont les ensembles de la partition
$\Cal F$ (les partitions de liaisons correspondantes \'etant les
partitions triviales en singletons).
\endexample

\proclaim{(2.3) Proposition} Tout lien non trivial $L$ d'un
hypergraphe $\Cal H$ est l'enveloppe $\Cal H$-convexe d'un ensemble de
cardinal 2.\quad \quad \qed
\endproclaim


\proclaim{(2.4) Proposition} Un hypergraphe arbor\'e d'ordre $n$ a au
maximum $n-1$ liens non triviaux.\quad \quad \qed
\endproclaim


\vskip.5cm
\subhead 3. DETERMINATION DES ARBRES DE BASE\endsubhead
\vskip.5cm


{\it La structure de liasion} d'un hypergraphe $\Cal H$ sur $X$ est
l'ensemble de ses liens, consid\'er\'e comme hypergraphe sur $X$ et
muni de la relation d'ordre $\subseteq$. Lorsque la structure de
liasion est consid\'er\'ee comme hypergraphe, les liens triviaux ne
jouent aucun r\^ole. Les propositions pr\'ec\'edentes indiquent que la
structure de liaison est plus simple (remarquablement plus simple, en
g\'en\'eral) que l'hypergraphe. N\'eanmoins, pour le probl\`eme qui
nous interesse ici, l'\'etude de la structure de liaison suffit: 

\proclaim{(3.1) Lemma fondamental} Soit $\Cal L$ la structure de
liaison d'un hypergraphe arbor\'e $\Cal H$. On a: $\Pi(\Cal L) =
\Pi(\Cal H)$.\quad \quad \qed
\endproclaim


\proclaim{(3.2) Th\'eor\graveaccent eme} Soit $\Cal H$ un hypergraphe
arbor\'e sur $X$ et soit $\Cal L$ l'ensemble de ses liens. Il existe
une bijection canonique de $\Pi(\Cal H)$ sur l'ensemble produit 
$$
\prod_{L\in\Cal L}\Pi_{Part(L)}.
$$
\endproclaim


\proclaim{(3.3) Corollaire} Soit $(L_i)_{1\leq i\leq m}$ la liste des
liens de l'hypergraphe arbor\'e $\Cal H$.\break Chaque lien $L_i$ a $l_i$
sommets, $c(i)$ composantes connexes de cardinalit\'es respectives
$c_{i,j}$, $1\leq j\leq c(i)$. Alors, les nombres d'arbres de base de
$\Cal H$ est donn\'e par la formule:
$$
|\Pi(\Cal H)|=\prod_{1\leq i\leq m}l^{c(i)-2}_i\prod_{1\leq j\leq
c(i)}c_{i,j}.
$$
\endproclaim

{\it Quelques indications sur la d\'emonstration:} en fait tout arbre
de base d'un hypergraphe arbor\'e $\Cal H$ peut \^etre construit par
extensions successives, en choisissant de proche en proche un arbre
sur chaque lien, obtenu par extension des arbres d\'ej\graveaccent a
contruits sur les liens plus petits. Il s'av\`ere que les choix
d'extensions possibles sont mutuellement ind\'ependants (cela
r\'esulte notamment des r\'esultats \'enonc\'es en annexe); comme
chaque extension est un cas o\`u s'applique le th\'eor\graveaccent eme
(1.5), on aboutit au th\'eor\`eme (3.2) et \graveaccent a son corollaire. Pour plus de d\'etails
voir \cite{6}.\quad \quad \qed


\vskip.5cm
\subhead 4. COMMENTAIRES ET APPLICATIONS\endsubhead
\vskip.5cm


(4.1) Il n'est pas tr\`es difficile de b\^atir un algorithme qui,
\'etant donn\'e un hypergraphe arbor\'e $\Cal H$ \graveaccent a $n$
sommets et $m$ ar\^etes, d\'etermine en temps $O(mn^3)$ la structure de
liaison et par l\`a, l'ensemble des arbres de base. Le nombre d'arbre
de base d'un hypergraphe arbor\'e $\Cal H$ est en g\'en\'eral
exponentiellement grand par rapport \graveaccent a $m$ et $n$, il est
donc clair que le comptage et la description compl\`ete de
$\Pi(\Cal H)$ ne peut se faire de mani\`ere rapide qu'en raison de la
structure produit (de longueur polynomiale en $n$) de l'ensemble
$\Pi(\Cal H)$, \'enonc\'ee par le th\'eor\graveaccent eme (3.2). A
tout arbre de base peut \^etre canoniquement associ\'e un code ``de
Pr\"ufer g\'en\'eralis\'e" dans l'ensemble produit
$$
\prod_{L\in\Cal L}\Pi_{Part(L)}.
$$
Ce code s'obtient par concat\'enation des codages de Pr\"ufer
g\'en\'eralis\'es associ\'es, selon le th\'eor\graveaccent eme (1.5),
aux sous-arbres induits par les liens modulo les partitions de liaison
correspondantes. 

\bigskip

(4.2) Le concept de structure de liaison rend possible la solution
d'un vieux pro\-bl\`eme (d\^u \graveaccent a Renz, cf\. \cite{6})
\graveaccent a savoir la caract\'erisation des hypergraphes de chemins
d'arbre, c'est \graveaccent a dire des hypergraphes arbor\'es
admettant un arbre de base $T$ qui induise un chemin sur chaque
ar\^ete de $\Cal H$. Une telle caract\'erisation, de type
``configurations exclues", a r\'ecemment \'et\'e obtenue par Arami et
l'auteur \cite{1}, aussi bien dans le cas orient\'e que non orient\'e.
La d\'emonstration de ces caract\'erisations permet la reconnaissance
de ces hypergraphes par un algorithme rapide, bas\'e sur l'algorithme
(4.1).

\bigskip

(4.3) Plus g\'en\'erallement, les m\'ethodes d\'evelopp\'ees ici
devraient permettre une organisation mieux structur\'ee des bases de
donn\'ees relationnelles existantes, puisque l'efficacit\'e d'une
telle organisation repose, en l'\'etat actuel de la question, sur les
hypergraphes arbor\'es (ou leur duaux) et sur la construction d'arbres
de base d'un type donn\'e pour ces hypergraphes. 

\bigskip

(4.4) Il est possible d'interpr\'eter les nombres d'arbres de base
d'un hypergraphe arbor\'e comme les d\'eterminants d'un certain type
de matrices qui, pour des raisons non encore \'elucid\'ees,
interviennent \'egalement en G\'eom\'etrie Alg\'ebrique (``$M$-matrices
de graphes alg\'ebriques"). Il semble int\'eressant dans ce contexte
de d\'evelopper des g\'en\'eralisations matricielles du
th\'eor\graveaccent eme (3.2), par analogie avec les r\'esultats
classiques sur l'\'enum\'eration des arbres couvrants d'un graphe
donn\'e. Cela sera l'objet d'un travail ult\'erieur. 



\vskip.5cm
\subhead ANNEXE: LIENS ET PARTITTONS SPECTRALES \endsubhead
\vskip.5cm


Nous allons donner une autre description de la structure de liaison
d'un hypergraphe arbor\'e, utile du point de vue algorithmique. Dans
toute cette section $\Cal H$ d\'esigne un hypergraphe sur $X$. Si
$\sigma$ est une partition quelconque de $X$, on note $\Cal H/\si $
l'hypergraphe quotient obtenu par contraction de chaque ensemble constitutif
de $\sigma$. Pour toute partition partielle $\tau\subseteq\sigma$, on note
$\hat\tau$ l'intersection de tous les ensembles $\Cal H$-convexes qui
rencontre chaque ensemble de $\tau$. 


\definition{(A.1) Definition} Le {\it spectre (d'ordre $1$)} d'un hypergraphe
$\Cal H$ sur $X$, not\'e $\text{sp} (\Cal H)$ est l'hypergraphe sur $X$
form\'e des liens non triviaux minimaux (pour l'inclusion). La {\it 
s\'equence spectrale} $S_1,\dots,S_{s}$ de $\Cal H$ est d\'efinie
r\'ecursivement par: 
\enddefinition

$$\left\{\matrix\format\l\\
S_1:=\text{sp}(\Cal H)\\
S_{k+1}:=\text{sp}(\Cal H/\sigma_k)\ \text{o\'u}\ \sigma_k\ \text{est la
partition de}\ X\ \text{form\'ee}\\ 
\text{\quad \quad \quad \quad des composantes connexes de}\ S_k.
\endmatrix\right .\tag A.2$$

Les $\sigma_k$ sont appel\'ees les {\it partitions spectrales} de
$\Cal H$. L'entier $s$ (la ``hauteur" de $\Cal H$) est le premier
indice tel que $S_{s+1}$ ne contienne aucune ar\^ete. La
d\'emonstration purement technique du lemme suivant est laiss\'e au
soin du lecteur:

\bigskip

\proclaim{(A.3) Lemme} Si $\Cal H$ est arbor\'e, chaque spectre $S_k$
(spectre de hauteur $k$) est une hyperfor\^et, c'est \graveaccent a
dire un hypergraphe sans aucun cycle. L'application $E\mapsto 
\hat E$
est une bijection entre l'ensemble des ar\^etes des spectres
successifs de $\Cal H$ et l'ensemble des liens non triviaux de
$\Cal H$. Une ar\^ete de $E$ de $S_k$ est l'image du lien $\hat
 E$ par
la surjection canonique $X \to X/ \sigma_k$; la partition $\sigma_k$
correspond par cette surjection \graveaccent a la partition de liaison
de $\hat E$.
\endproclaim

Une description des arbres de base de $\Cal H$ et une d\'emonstration
du th\'eor\graveaccent eme (3.2) sont obtenus \graveaccent a partir du
r\'esultat suivant o\`u $\sigma_0$ d\'esigne la partition triviale de
$X$ en singletons:

\bigskip

\proclaim{(A.4) Th\'eor\graveaccent eme} Si $\Cal H$ est un
hypergraphe arbor\'e, les arbres de base pour $\Cal H$ sont exactement
les arbres $T$ sur $X$ tels que chaque quotient $T/\sigma_{k-1}$ soit,
pour $1\leq k\leq s$, un arbre de base de $S_k$.
\endproclaim

\Refs\widestnumber\key{10}

\ref\key 1\by Z. Arami, P. Duchet \book Systems of paths in a
tree\bookinfo en preparation 
\vol \pages \endref

\ref\key 2\by C. Berge \book Hypergraphes \publ Gauthiers-Vilars
\publaddr Paris \yr 1987 \pages \endref

\ref\key 3\by A. Cayley  \paper
A theorem on trees \jour Quart\. J. Math\.
\vol 23 \yr 1889 \pages 376--378 \endref

\ref\key 4\by P. Duchet  \paper Propri\'et\'e de Helly et
probl\`emes de repr\'esentation \jour Proc\. Int\. Coll\. CNRS 
\vol 260 \publ CNRS \publaddr Paris \yr 1978 \pages 117--118 \endref

\ref\key 5\by P. Duchet  \paper Classical Perfect Graphs, an
introduction with emphasis on triangulated and interval graphs \jour
Ann\. Disc\. Math\. 
\vol 21 \yr 1984 \pages 67--96 \endref 

\ref\key 6\by P. Duchet  \book Tree hypergraphs and their basic
trees \publ Preprint \publaddr Univ\. Paris~6 \yr 1985 \pages \endref 

\ref\key 7\by P. Duchet  \paper La convexit\'e dans les structures
combinatoires \inbook Actes du S\'emin\. Lotharingien, 12$^{\text{e}}$
Session \publ Kleebach
 \yr 1985 \pages 67--107\endref 

\ref\key 8\by C. Flament  \paper Hypergraphes arbor\'es \jour
Discrete Math\.
\vol 21 \yr 1978 \pages 223--226 \endref 

\ref\key 9\by L. Lov\'asz  \book Combinatorial problems and
exercises \publ North Holland Pub\. Co. \publaddr Amsterdam--New
York--Oxford
\vol  \yr 1979 \pages \endref

\ref\key 10\by J. W. Moon  \paper Enumerating labelled trees\inbook
 Graph Theory and Theoretical Physics\ed F. Harary \publ
Acad\. Press \publaddr London--New York \yr 1967 \pages 261--271
\endref

\ref\key 11 \by A. Pr\"ufer  \paper \jour Archiv Math\. Phys\. \vol
27 \yr 1918 \pages 142--144 \endref 

\ref\key 12 \by P. J. Slater  \paper A characterization of soft
hypergraphs \jour Canad\. Math\. Bull\. \vol 21 \yr 1978 \pages 335--337 \endref

\endRefs


\end{document}
</pre></body></html>