图形:在小于O(| V |)的范围内找到一个接收器-或表明它无法完成 我有一个图，其中有 n 个节点作为邻接矩阵. 是否可以在少于 O(n)的时间内检测到下陷? 如果是，怎么办?如果没有，我们如何证明呢? 下沉顶点是一个顶点，该顶点具有来自其他节点的传入边，而没有传出边. 解决方案 相反，假设存在一种查询少于(n-2)/2条边的算法，并让对手任意回答这些查询.根据鸽子洞原理，存在(至少)两个节点v，w，它们不是所查询的任何边的端点.如果算法 .. 发布时间：2021-04-02 20:30:10 algorithm graph computer-science graph-theory sink-vertex 其他开发
