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].
- ↑ Dasgupta 1999.
- ↑ Deo 1974, p. 206.
- ↑ Harary et Sumner (1980).
- ↑ Simion 1991.
- ↑ Kim et Pearl 1983.
- ↑ Rebane et Pearl 1987.