junction_tree#

junction_tree(G)[source]#

返回给定图的关联树。

关联树（或团树）由给定的（无）有向图 G 构建。该树基于 G 的道德化和三角化版本构建。树的节点由修订后图的极大团和分隔集组成。两个团的分隔集是这些团节点集合的交集，例如，(A,B,C) 和 (A,C,E,F) 的分隔集是 (A,C)。在相关文献中，这些节点通常被称为“变量”。关联树是二分图，其中每个分隔集连接到其对应的两个团。

关联树不是唯一的，因为考虑团的顺序决定了包含哪些分隔集。

关联树算法包含五个步骤 [1]

  1. 道德化图

  2. 三角化图

  3. 找到极大团

  4. 从团构建树，连接共享节点的团，将边权重设置为共享变量的数量

  5. 找到最大生成树

参数:
Gnetworkx.Graph

有向图或无向图。

返回:
junction_treenetworkx.Graph

G 的对应关联树。

引发:
NetworkXNotImplemented

如果 G 是 MultiGraph 或 MultiDiGraph 的实例，则引发此异常。

参考资料

[2]

Finn V. Jensen and Frank Jensen. 1994. Optimal junction trees. In Proceedings of the Tenth international conference on Uncertainty in artificial intelligence (UAI’94). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 360–366.

在本页