find_asteroidal_triple

find_asteroidal_triple(G)

在给定图中寻找一个星形三元组。

星形三元组是指三个非相邻顶点的集合，其中任意两个顶点之间存在一条路径，该路径避开了第三个顶点的闭邻域。它检查所有独立的顶点三元组，并确定它们是否为星形三元组。这一过程借助一种称为组件结构的数据结构来完成。 组件结构编码了关于在移除给定顶点的闭邻域后，哪些顶点属于同一连通组件的信息。用于检查的算法是[R8fa0882fc70e-1]_中概述的平凡算法，其运行时间为：math:O(|V||overline{E} + |V||E|) ，其中第二项是创建组件结构的时间。

Parameters:

GNetworkX 图

要检查是否为AT-free的图

Returns:

列表或None

星形三元组以节点列表的形式返回。如果不存在星形三元组，即图是AT-free，则返回None。返回值取决于certificate参数。默认选项是一个布尔值，如果图是AT-free，即给定图不包含星形三元组，则返回True，否则返回False，即如果图包含至少一个星形三元组。

Notes

组件结构和算法在[R8fa0882fc70e-1]_中描述。当前实现为简单图实现了平凡算法。

References

[1]

Ekkehard Köhler, “Recognizing Graphs without asteroidal triples”, Journal of Discrete Algorithms 2, pages 439-452, 2004. https://www.sciencedirect.com/science/article/pii/S157086670400019X