is_chordal

is_chordal(G)

检查图 G 是否为弦图。

如果图 G 中每个长度至少为 4 的圈都存在弦（连接圈中两个不相邻节点的边），则称该图为弦图。

参数：

G图

一个 NetworkX 图对象。

返回：

chordal布尔值

如果 G 是弦图则返回 True，否则返回 False。

引发：

NetworkXNotImplemented

该算法不支持 DiGraph、MultiGraph 和 MultiDiGraph。

说明

该例程尝试通过最大势搜索遍历每个节点。当发现任何节点的割集不是团时，返回 False。基于 [1] 中的算法。

忽略自环。

参考文献

[1]

R. E. Tarjan and M. Yannakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput., 13 (1984), pp. 566–579.

示例

>>> e = [
...     (1, 2),
...     (1, 3),
...     (2, 3),
...     (2, 4),
...     (3, 4),
...     (3, 5),
...     (3, 6),
...     (4, 5),
...     (4, 6),
...     (5, 6),
... ]
>>> G = nx.Graph(e)
>>> nx.is_chordal(G)
True