find_asteroidal_triple#

find_asteroidal_triple(G)[源代码]#

在给定的图表中找到一个小行星三元组。

小行星三元组是不相邻顶点的三元组,使得它们中的任何两个之间都存在一条路径,从而避免了第三个顶点的封闭邻域。它检查所有独立的顶点三元组,以及它们是否是小行星三元组。这是在称为组件结构的数据结构的帮助下完成的。当从图中移除给定顶点的闭合邻域时,组件结构编码关于哪些顶点属于同一连通组件的信息。用于检查的算法很简单,如 [1], ,它的运行时为 \(O(|V||\overline{{E}} + |V||E|)\) ,其中第二个术语是组件结构的创建。

参数
G网络X图表

要检查的图是否为AT-Free

返回
列表或无

小行星三元组作为节点列表返回。如果没有小行星三重存在,即图是自由的,则不返回任何一个。返回的值取决于证书参数。默认选项是bool,如果图形处于空闲状态,即给定图形不包含小行星三元组,则为true;否则为false,即图形至少包含一个小行星三元组。

笔记

中描述了组件结构和算法 [1]. 当前的实现实现了简单图的平凡算法。

工具书类

1(1,2)

Ekkehard Kóhler,“识别没有小行星三元组的图形”,《离散算法学报》第2期,第439-4522004页。https://www.sciencedirect.com/science/article/pii/s15708667010019x