Note

This documents the development version of NetworkX. Documentation for the current release can be found here.

networkx.algorithms.chordal.is_chordal

is_chordal(G)[source]

Checks whether G is a chordal graph.

A graph is chordal if every cycle of length at least 4 has a chord (an edge joining two nodes not adjacent in the cycle).

Parameters
Ggraph

A NetworkX graph.

Returns
chordalbool

True if G is a chordal graph and False otherwise.

Raises
NetworkXNotImplemented

The algorithm does not support DiGraph, MultiGraph and MultiDiGraph.

Notes

The routine tries to go through every node following maximum cardinality search. It returns False when it finds that the separator for any node is not a clique. Based on the algorithms in [1].

References

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.

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