junction_tree#

junction_tree(G)[source]#

返回给定图的连接树。

连接树（或团树）是从一个（无）向图 G 构建的。该树基于 G 的道德化和三角化版本构建。树的节点由修正图的最大团和分离集组成。两个团的分离集是这些团节点的交集，例如，(A,B,C) 和 (A,C,E,F) 的分离集是 (A,C)。这些节点在此文献中通常称为“变量”。该树是二分的，每个分离集与其两个团相连。

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

连接树算法包括五个步骤 [1]：

  1. 道德化图

  2. 三角化图

  3. 找到最大团

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

  5. 找到最大生成树

Parameters:
Gnetworkx.Graph

有向或无向图。

Returns:
junction_treenetworkx.Graph

G 对应的连接树。

Raises:
NetworkXNotImplemented

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

References

[2]

Finn V. Jensen 和 Frank Jensen。1994。最优连接树。在第十届国际人工智能不确定性会议（UAI’94）的会议记录中。Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 360–366.

On this page