基于连通性的无向随机图的邻接矩阵重组

Question

我有一个无向随机图的nxn邻接矩阵A，所以Aij可以是0 或 1。如果 Aij 是 1 这意味着 ith 和 [=17 之间有一条边=]th个节点。如果是 0 则表示它们之间没有边。

我想根据顶点的度数重新排列矩阵。所有度小于等于k的顶点，我想把它们放在最后。假设有 m 这样的顶点，那么我的新邻接矩阵的最后 m 行和列将代表这些顶点。

我想在 MATLAB 中实现它。我不知道如何有效地解决它。只有一个人认为我知道如何找到这样的顶点。

a = 1:n;
ver = a(sum(A) < k+1 );

感谢任何帮助。

Answer 1

由于您的图形是无向的，因此您的邻接矩阵 A 是对称的。正如您已经注意到的，您可以简单地通过对 A:

的行（或列）求和来判断顶点的度数

deg = sum(A, 2);

现在您可以sort根据顶点的度数

[sd si] = sort(deg, 'decrease'); %// sort in a decreasing order

您可以使用已排序的索引 (si) 重新排列 A:

A = A(si,si);

请注意，您必须对A的行和列应用相同的排列，否则...

既然你的图是按顶点的度数排序的，那么度数较小的一次自然会在 A 的末尾。