Polyarbre

Toute arborescence est un polyarbre, mais la réciproque est fausse : un polyarbre n'est pas toujours une arborescence. Tout polyarbre est un multiarbre, c'est-à-dire un graphe orienté sans cycle dans lequel, pour tout sommet, le sous-graphe accessible depuis un sommet est un arbre.

La relation d'accessibilité entre les sommets d'un polyarbre est un ordre partiel qui a une dimension d'ordre (en) au plus trois. Si la dimension d'ordre est égale à 3, il existe un sous-ensemble de 7 éléments ${\displaystyle x,y_{i}(i=1,2,3),z_{i}(i=1,2,3)}$ tels que pour chaque ${\displaystyle i}$, on a ${\displaystyle x\leq y_{i}\geq z_{i}}$ ou ${\displaystyle x\geq y_{i}\leq z_{i}}$ ; ces six inégalités définissent une structure de polyarbre sur les sept éléments[7]

Un fence (en) ou ensemble zigzag est un cas particulier d'un polyarbre où le graphe sous-jacent est une chaîne et les arcs le long de la chaine ont des orientations alternantes. L'ordre d’accessibilité dans un polyarbre a aussi été appelé generalized fence[8].

Le nombre de polyarbre distincts à n sommets non étiquetés est, pour n = 1, 2, 3, ..., , la donné par la suite :

1, 1, 3, 8, 27, 91, 350, 1376, 5743, 24635, 108968, 492180, ... (c'est la suite A000238 de l'OEIS)

Un tournois à 6 sommets contenant un exemplaire de tout polyarbre à 4 sommets.

La conjecture de Sumner, nommée ainsi d'après David Sumner, affirme que les tournois sont des graphes universels pour les polyarbres, en ce sens que tout tournoi avec ${\displaystyle 2n-2}$ sommet contient tout polyarbre avec n sommets comme sous-graphe. Cette conjecture, même si elle est encore ouverte dans le cas général, a été démontré pour toutes les valeurs suffisamment grandes de n[9].

Les polyarbres ont été utilisés comme modèle graphique en raisonnement probabiliste[1]. Si un réseau bayésien a une structure de polyarbre, la propagation des convictions peut être utilisée pour effectuer une inférence efficacement [5] - [6].

L'arbre de contour (en) (aussi appel le graphe de Reeb) d'une fonction à valeur réelles sur une espace vectoriel est un polyarbre qui décrit les lignes de niveau de la fonction. Les nœuds de l'arbre de contour sont les lignes de niveau qui passent par un point critique de la fonction, et les arcs décrivent des ensembles contigus d'ensembles de niveaux sans point critique. L'orientation d'un arc est déterminée par la comparaison des valeurs des fonctions sur les deux ensembles de niveaux correspondants[10].

• Lexique de la théorie des graphes