小行星三重

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

图 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)	检查图是否是 AT-free 图。
find_asteroidal_triple(G)	在给定图中查找一个小行星三重。