Peut-être isnt même un DAG, mais comme dénomination im après que je n'étais pas sûr de ce titre pour donner cette ...Quel est le nom de ce type de graphique acyclique dirigé?
Quel est le nom d'une structure de données où chaque noeud ne peut avoir des chemins 0 ou 1 DEDANS ? Strictement, est-ce un arbre?
Merci
C'est un arbre dirigé. Les arbres ordinaires en tant que tels ne sont pas dirigés. Votre contrainte n'est pas précisément comment les arbres sont définis (la définition d'un arbre est que deux sommets sont connectés par pas plus d'un chemin), mais il contraint votre graphique à être un arbre dirigé valide. (À moins que vous ne vouliez utiliser des usages bizarres d '«arbre dirigé» qui nécessitent un tropisme uniforme, ce que je ne peux pas dire m'intéresse.)
Y a-t-il d'autres contraintes? De seulement celui que vous avez donné je peux construire un graphique qui est pas un arbre.
A -> B -> A
Si vous ajoutez la contrainte que le graphe est acyclique, alors il serait un arbre.
Comment ça? Il peut faire A -> B -> {C, D, E} .... J'ai l'impression qu'il me manque quelque chose. – chaos
Oh, je vois. Je pense que vous lisez une implication d'une contrainte sur les liens externes. Mais cela semble impossible, puisque la seule contrainte que vous pourriez lire de la question d'OP serait zéro outlinks, ce qui vous empêcherait d'avoir un graphique du tout. – chaos
@chaos: Je pense que vous avez commencé à écrire votre commentaire avant d'éditer ma réponse. Il me manquait quelque chose avant le montage. –
merci pour la clarification –
Par Bill le Lézard, il nécessite la contrainte d'acyclicité. Je l'ai supposé de toutes les mentions, bien que ce ne soit pas réellement dans votre spécification finale. – chaos
Ouais je voulais dire acyclique, déduit du titre mais j'aurais dû être plus précis;) –