is_regular_expander

is_regular_expander(G, *, epsilon=0)

确定图 G 是否为正则扩展图。[1]

扩展图是一种稀疏图，具有强大的连通性特性。

更确切地说，此辅助函数检查图是否为正则的 \((n, d, \lambda)\)-扩展图，其中 \(\lambda\) 接近 Alon-Boppana 界限，并由 \(\lambda = 2 \sqrt{d - 1} + \epsilon\) 给出。[2]

在 \(\epsilon = 0\) 的情况下，如果图成功通过测试，则它是一个 Ramanujan 图。[3]

Ramanujan 图具有几乎最大的谱隙，这使得它们成为优秀的扩展图。

Parameters:

GNetworkX 图

epsilonint, float, 默认值=0

Returns:

bool

给定图是否为正则的 \((n, d, \lambda)\)-扩展图，其中 \(\lambda = 2 \sqrt{d - 1} + \epsilon\)。

See also

maybe_regular_expander

random_regular_expander_graph

References

[1]

扩展图, https://en.wikipedia.org/wiki/Expander_graph

[2]

Alon-Boppana 界限, https://en.wikipedia.org/wiki/Alon%E2%80%93Boppana_bound

[3]

Ramanujan 图, https://en.wikipedia.org/wiki/Ramanujan_graph

Examples

>>> G = nx.random_regular_expander_graph(20, 4)
>>> nx.is_regular_expander(G)
True