Polyarbre
De Wikipedia, l'encyclopédie encyclopedia
En mathématiques, et notamment en théorie des graphes, un polyarbre[1] (aussi appelé arbre dirigé[2], arbre orienté[3],[4] ou singly connected network[5]) est graphe orienté acyclique dont le graphe non orienté sous-jacent est un arbre (théorie des graphes). En d'autres termes, si on remplace les arcs par des arêtes, on obtient un graphe non orienté qui est à la fois connexe et sans cycle.
Une polyforêt (ou forêt dirigée ou forêt orientée) est un graphe orienté dont le graphe non orienté sous-jacent est une forêt. Autrement dit, si on remplace les arcs orientés par des arêtes, on obtient un graphe non orienté qui est sans cycles.
La terminologie « polytree » a été introduite en 1987 par George Rebane et Judea Pearl[6].