Worldlex Wiki En combinatoire et en théorie de l'ordre , un multitree peut décrire l'une ou l'autre de deux structures équivalentes : un graphe acyclique orienté (DAG) dans lequel il existe au plus un chemin orienté entre deux sommets quelconques , ou de manière équivalente dans lequel le sous-graphe accessible depuis n'importe quel sommet induit un arbre non orienté , ou un ensemble partiellement ordonné (poset) qui ne comporte pas quatre éléments théorie de la complexité computationnelle , les multitrees ont également été appelés graphes fortement non ambigus ou mangroves ; ils peuvent être utilisés pour modéliser des algorithmes non déterministes dans lesquels il existe au plus un chemin de calcul reliant deux états quelconques.
Les multitrees peuvent être utilisés pour représenter plusieurs taxonomies se chevauchant sur un même ensemble de base. Si un arbre généalogique peut contenir plusieurs mariages entre familles, mais ne contient aucun mariage entre deux personnes apparentées par le sang, alors il forme un multitree.
d'accessibilité est un ordre partiel sans diamant. Réciproquement, dans un ordre partiel sans diamant, la réduction transitive identifie un graphe acyclique orienté dont le sous-graphe accessible depuis n'importe quel sommet induit un arbre non orienté.Familles sans diamant
Une famille d'ensembles sans diamant est une famille F d'ensembles dont l'ordre d'inclusion forme un ensemble partiellement ordonné sans diamant. Si D ( n ) désigne la plus grande famille possible de sous-ensembles sans diamant d'un ensemble à n éléments, alors on sait que
et on conjecture que la limite est 2.
Structures apparentées
Un polytree , un graphe acyclique orienté formé en orientant les arêtes d'un arbre non orienté, est un cas particulier de multitree.
Le sous-graphe accessible depuis n'importe quel sommet d'un multitree est une arborescence enracinée dans le sommet, c'est-à-dire un polytree dans lequel toutes les arêtes sont orientées à l'opposé de la racine.
Le mot « multitree » a également été utilisé pour désigner un ordre partiel série-parallèle , ou d’autres structures formées en combinant plusieurs arbres.
Plus d articles de Worldlex Wiki
Revenez a l index pour explorer davantage de pages sur l histoire, la science, la culture, la geographie et la societe en francais.
Explorer l index