Asteroidal

图中的星形三元组和星形数的算法。

图 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（Asteroidal Triple）图。
find_asteroidal_triple(G)	在给定图中寻找一个星形三元组。