图:找到小于O(| V |)的接收器 - 或者显示无法完成

Question

我有一个图表,n节点作为邻接矩阵.

是否有可能在不到O(n)时间内检测到水槽？

如果有,怎么样？如果不是,我们如何证明呢？

接收器顶点是一个顶点,具有来自其他节点的入射边缘,没有出射边缘.

Answer 1

阅读SPWorley提供的链接我被提醒锦标赛树算法找到数字数组中的最小元素.树顶部的节点是最小元素.由于链路中的算法也谈到了两个节点之间的竞争(v,w),如果v-> w则由w继承.我们可以使用类似于找到最小元素的算法来找出接收器.但是,无论是否存在接收器,都返回节点.但是,如果存在接收器,则总是返回.因此,我们最终必须检查返回的节点是否为接收器.

//pseudo code
//M -> adjacency matrix
int a=0
for(int i=1;i<vertices;++i)
{
  if(M[a,i]) a=i;
}

//check that a is sink by reading out 2V entries from the matrix
return a; //if a is a sink, otherwise -1

Answer 2

此页面可以回答您的确切问题.线性时间算法是

   def find-possible-sink(vertices):
     if there's only one vertex, return it
     good-vertices := empty-set
     pair vertices into at most n/2 pairs
     add any left-over vertex to good-vertices
     for each pair (v,w):
       if v -> w:
         add w to good-vertices
       else:
         add v to good-vertices
     return find-possible-sink(good-vertices)

   def find-sink(vertices):
     v := find-possible-sink(vertices)
     if v is actually a sink, return it
     return "there is no spoon^H^H^H^Hink"

Answer 3

相反，假设存在一种查询少于 (n-2)/2 个边的算法，并让对手任意回答这些查询。根据鸽洞原理，（至少）存在两个节点 v、w，它们不是所查询的任何边的端点。如果算法输出 v，那么对手会通过将每条边与接收器 w 一起放入而犯错误，如果算法输出 w，则类似。