find_asteroidal_triple

find_asteroidal_triple(G)

在给定图中查找类星形三元组。

类星形三元组是三个互不相邻的顶点构成的三元组，其中任意两个顶点之间都存在一条路径，且该路径避开第三个顶点的闭邻域。该函数检查所有独立的顶点三元组，判断它们是否为类星形三元组。这借助了一种称为连通分量结构的数据结构来完成。连通分量结构编码了关于当从图中移除给定顶点的闭邻域时，哪些顶点属于同一连通分量的信息。用于检查的算法是[1]中概述的朴素算法，其运行时间为 \(O(|V||\overline{E} + |V||E|)\)，其中第二项是创建连通分量结构的时间。

参数:

GNetworkX 图

要检查是否为AT-free的图。

返回:

list 或 None

如果找到类星形三元组，则以节点列表的形式返回。如果不存在类星形三元组（即图是AT-free的），则返回 None。

注意

连通分量结构和算法在[1]中描述。当前实现是针对简单图的朴素算法实现。

参考文献

[1] (1,2)

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