complete_to_chordal_graph

complete_to_chordal_graph(G)

返回一个将 G 补全为弦图的副本

向 G 的副本添加边以创建一个弦图。一个图 G=(V,E) 被称为弦图，如果对于每个长度大于 3 的环，存在两个非相邻节点通过一条边（称为弦）连接。

Parameters:

GNetworkX 图

无向图

Returns:

HNetworkX 图

G 的弦图增强

alpha字典

G 的节点消除顺序

Notes

计算图的弦图增强有不同的方法。这里使用的算法称为 MCS-M，给出了图的至少最小（局部）三角剖分。注意，这种三角剖分不一定是全局最小。

https://en.wikipedia.org/wiki/Chordal_graph

References

[1]

Berry, Anne & Blair, Jean & Heggernes, Pinar & Peyton, Barry. (2004) 用于计算图的最小三角剖分的最大基数搜索。算法学报。39. 287-298. 10.1007/s00453-004-1084-3.

Examples

>>> from networkx.algorithms.chordal import complete_to_chordal_graph
>>> G = nx.wheel_graph(10)
>>> H, alpha = complete_to_chordal_graph(G)