is_chordal

is_chordal(G)

检查图 G 是否为弦图。

一个图是弦图，如果每个长度至少为 4 的环都有一条弦（连接环中不相邻两个节点的边）。

Parameters:

G图

一个 NetworkX 图。

Returns:

chordalbool

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

Raises:

NetworkXNotImplemented

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

Notes

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

自环被忽略。

References

[1]

R. E. Tarjan 和 M. Yannakakis，简单的线性时间算法 用于测试图的弦性，测试超图的无环性，以及 选择性地简化无环超图，SIAM J. Comput., 13 (1984), pp. 566–579.

Examples

>>> 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