Multi-arbre
From Wikipedia, the free encyclopedia
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 a ≤ b ≤ d et a ≤ c ≤ d mais où b et c sont incomparables (un tel ensemble ordonné est aussi appelé diamond-free poset (ou ordre partiel sans diamant)[1].
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 la plus grande famille de parties sans diamant d'un ensemble à n éléments, on a
et il est conjecturé[1] que la limite est 2.
