Polytree

Dans la théorie de graphique , un polytree est un graphique avec tout au plus un chemin non dirigé entre deux sommets quelconques. En d'autres termes, un polytree est un graphique acyclique dirigé par (le DAG) pour lequel il n'y a aucun cycle non dirigé non plus. Le " nommé ; polytree" ; a été inventé par Rebane et Pearl (1987), et désigné parfois sous le nom du " ; network" séparément relié ; (Kim et Pearl, 1983).

Chaque arbre dirigé est un polytree, mais non chaque polytree est un arbre dirigé. L'image du côté droit montre à un polytree ce qui n'est pas un arbre dirigé. Pour les arbres , si dirigé, chaque noeud devrait avoir l'indegree 0 ou 1.

Polytrees souvent sont produits dans les réseaux bayésiens en fait, quelques problèmes peut être résolu dans les polytrees dans le temps polynôme mais prendre les réseaux exponentiels de temps en général.

Random links: