假设给出了一个无向图G,该图的n顶点和m边由n x n邻接矩阵A表示,并且给出了顶点S的子集(由大小为m的数组表示)。如何检查S是否是具有二次时间和空间复杂性的G的顶点覆盖?根据顶点覆盖的定义,我知道我们要求每个边都必须与包含在S中的顶点相关联。
我可以很容易地提出一个三次算法:遍历邻接矩阵;每个1表示一个边缘(u, v)。检查u还是v在S中。如果没有,答案是否定的。如果我们到达邻接矩阵</
我正试图找到一种用Python计算Hermitian邻接矩阵的pythonic方法,我真的很挣扎。这幅图像显示了Hermitian邻接矩阵的定义:它的工作原理如下。如果有一个来自i to j和j to i的有向边,那么位置i,j处的相应矩阵值应该设置为1。如果只有来自i to j的有向边,那么位置i,j处的矩阵元素应该设置为+i。如果从j to i只有一个有向边,那么位置i,j处的矩阵元素应该设置为-i。