小行星的

图中小行星三重态和小行星数的算法。

图G中的小行星三元组是三个非相邻顶点u、v和w的集合,使得它们之间存在一条路径,避免了第三的封闭邻域。更正式地说,v_j,v_k属于g-n的同一个连通分量 [v_i] ,其中n [v_i] 表示v_i的闭邻域。不包含任何小行星三元组的图称为at-free图。at-free图类是多项式时间内许多np完全问题可解的图类。其中,独立集与着色。

is_at_free (g)

检查图表是否空闲。

find_asteroidal_triple (g)

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