chordal_graph_treewidth

chordal_graph_treewidth(G)

返回弦图 G 的树宽。

Parameters:

G图

一个 NetworkX 图

Returns:

treewidthint

图中最大团的大小减一。

Raises:

NetworkXError

该算法不支持 DiGraph、MultiGraph 和 MultiDiGraph。 该算法只能应用于弦图。如果输入的图被发现是非弦图，则引发 NetworkXError 。

References

[1]

https://en.wikipedia.org/wiki/Tree_decomposition#Treewidth

Examples

>>> e = [
...     (1, 2),
...     (1, 3),
...     (2, 3),
...     (2, 4),
...     (3, 4),
...     (3, 5),
...     (3, 6),
...     (4, 5),
...     (4, 6),
...     (5, 6),
...     (7, 8),
... ]
>>> G = nx.Graph(e)
>>> G.add_node(9)
>>> nx.chordal_graph_treewidth(G)
3