二次时间顶点覆盖率验证 [英] Quadratic-time vertex cover verification

问题描述

假设您获得了一个无向图G，该图具有n个顶点和m个顶点 n x n邻接矩阵A表示的边，您也 给定顶点S的子集(由大小为m的数组表示). 如何检查S是否是G的顶点覆盖且具有二次方 时间和空间的复杂性?

Suppose you are given an undirected graph G with n vertices and m edges represented by an n x n adjacency matrix A, and you are also given a subset of vertices S (represented by an array of size m). How can you check whether S is a vertex cover of G with quadratic time and space complexity?

根据顶点覆盖的定义，我知道我们要求每个边都必须入射到S中包含的顶点.

By the definition of a vertex cover, I know that we require every edge must be incident to a vertex that's contained in S.

我可以轻松地提出三次算法:遍历邻接矩阵；每个1表示边(u, v).检查S中是否包含u或v.如果不是，答案是否定的.如果我们到达邻接矩阵的末尾，答案是肯定的.

I can easily come up with a cubic algorithm: iterate over the adjacency matrix; each 1 represents an edge (u, v). Check whether u or v are in S. If not, the answer is no. If we get to the end of the adjacency matrix, the answer is yes.

但是如何在O(n^2)时间内完成此操作?我猜到目前为止，我所做的唯一真正的观察"是，如果我们已经在S中找到了与该行相对应的顶点，则可以在遍历邻接矩阵时跳过中间行.但是，这对我没有太大帮助.

But how can I do this in O(n^2) time? I guess the only real "observation" I've made so far is that we can possibly skip intermediate rows while iterating over the adjacency matrix if we've already found the vertex corresponding to that row in S. However, this has not helped me very much.

有人可以帮助我(或为我指明正确的方向)吗?

Can someone please help me (or point me in the correct direction)?

谢谢

推荐答案

构造一个数组T，该数组是所有不在S中的元素的位置.

Construct an array T which is the positions of all of the elements NOT in S.

然后:

for i in T:
    for j in T:
        if A[i][j] == 1:
            return False
return True

这篇关于二次时间顶点覆盖率验证的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！