Multi-arbre

Un réseau papillon, un multi-arbre utilisé en calcul distribué, montrant (en rouge) le sous-arbre accessible depuis un de ses nœuds.

Modèle:Article connexe En combinatoire et en théorie des ordres, le terme multi-arbre peut décrire l'une des deux structures suivantes : un graphe orienté acyclique dans lequel l'ensemble des sommets accessibles depuis un nœud est toujours un arbre, ou un ensemble partiellement ordonné dans lequel il n'existe pas quatre éléments a, b, c, et d qui forment un sous-ordre en diamant, avec Modèle:Nobr et Modèle:Nobr mais où b et c sont incomparables (un tel ensemble ordonné est aussi appelé diamond-free poset (ou ordre partiel sans diamant).

Équivalence entre les définitions

Dans un graphe orienté acyclique, si l'ensemble des sommets accessibles depuis n'importe quel sommet induit un arbre, ou de manière équivalente, s'il existe au plus un chemin orienté entre n'importe quelle paire de sommets, alors sa relation d'accessibilité est un ordre partiel sans diamant. Réciproquement, dans un ordre partiel, s'il est sans diamant alors sa réduction transitive induit un graphe orienté acyclique dans lequel l'ensemble des sommets accessibles depuis n'importe quel sommet induit un arbre.

Familles sans diamant

Une famille d'ensembles est une famille F d'ensemble pour lequel l'ordre d'inclusion est sans diamant. Notons $D(n)$ la plus grande famille de parties sans diamant d'un ensemble à n éléments, on a

$2\le \underset{n\to \mathrm{\infty }}{\lim }\frac{D(n)}{(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })}\le 2+\frac{3}{11}$

et il est conjecturé que la limite est 2.

Applications

Les multi-arbres peuvent être utilisés pour représenter des taxonomies multiples chevauchantes sur un même ensemble.

Si un arbre généalogique contient plusieurs mariages entre des membres de deux familles distinctes mais pas de mariages entre des membres de la même famille, il prend la forme d'un multi-arbre. Dans le contexte de la théorie de la complexité, les multi-arbres ont aussi été appelés « graphes fortement non-ambigus » ou « mangroves » ; ils servent à modéliser les algorithmes non déterministes où il existe au plus un chemin de calcul qui connecte deux états.

Structures voisines

Un polyarbre est un graphe orienté acyclique obtenu en orientant chaque arête d'un arbre (théorie des graphes) ; c'est un cas particulier d'un multi-arbre.

L'ensemble des nœuds connecté à un nœud donné u dans un multi-arbre est une arborescence.

Le mot « multitree » a aussi été utilisé pour désigner un Modèle:Lien.