如何对有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的1都集中到对角线以上？
对角线,矩阵,顶点
已帮助 人
-
正确答案：可以按各顶点的出度进行排序。n个顶点的有向图其顶点最大出度是n一1最小出度为O。这样排序后出度最大的顶点编号为1出度最小的顶点编号为n。之后进行调整即若存在弧<ij>而顶点j的出度大于顶点i的出度则将把j编号在顶点i的编号之前。
可以按各顶点的出度进行排序。n个顶点的有向图,其顶点最大出度是n一1,最小出度为O。这样排序后,出度最大的顶点编号为1,出度最小的顶点编号为n。之后,进行调整,即若存在弧<i,j>,而顶点j的出度大于顶点i的出度,则将把j编号在顶点i的编号之前。