Polytree

置信度传播由美国计算机科学家朱迪亚·珀尔于1982年提出。最初该算法的运用范围仅限于树，不久则扩展到多树（英语：Polytree）。此后，研究者发现在一般的图中该算法是一种十分有用的近似算法。 Braunstein, A.; Mézard, M.; Zecchina, R

中I为单位矩阵。因为一个有向无环图不允许自环，它的邻接矩阵的对角线必定全为0。因此，加上I保持了所有矩阵因子都是0或1的特性。 多重树（英语：polytree）由将自由树的边定向（英语：orienting）而得到。 多重树必定是有向无环图。对于有根树，将其所有边赋予指离根的方向也可以得到有向无环图，即树状图。