在多项式时间内找到图中的向日葵子图。

Question

图G的一个子图Sn是一个向日葵图，如果由n个顶点的圈Cn = {v1，v2，...，vn}和其他n个独立的顶点{u1，u2，...，un}组成，使得对于每个i，ui与vi和vj相邻，其中j= i-1(mod )。

Answer 1

你可以把向日葵-在这个问题的意义上-想象成一个三角形的循环。在O(N^3)时间内，您可以检查每个点的三元组，以确定它是否为三角形，并创建一个新图，该图的顶点表示原始图中的三角形，并且如果两个三角形共享一个或多个顶点，则两个顶点连接在一起。

然后，深度优先搜索寻找后边应该会在这个图中找到循环。并不是所有的周期都是好的。我认为，检查派生图中假设的循环中没有两条连续的边是由原始图中的相同顶点生成的就足够了，并且您可以将此作为深度优先搜索的一部分进行检查。可能需要对案例进行一些详细的分析才能确定这一点，除非你能找到一个整洁的证据。