无爪图

Question

我一直在阅读这个wiki文章关于如何找到图是否是无爪的，但我无法理解其中的某些部分。

算法说(在识别标题下) "...one可以通过检查图的每个顶点来测试图是否是无爪的，其邻域的补图不包含三角形“。

现在，我们可以通过简单计算G*G*G来检验一个图(用邻接矩阵表示)是否包含一个三角形，如果它的迹(所有主要对角元素之和)为零，则不存在三角形。

什么是“对于图的每个顶点，它的邻域的补图”？

这是否意味着我应该对每个顶点取图的补，并检查三角形是否为三角形。

Answer 1

对于每个顶点，你接受由这个顶点导出的子图，它是相邻的。然后，取每一个子图的补图，独立地检查每个子图的三角形。