0

我想生成具有 N 个节点的无向​​图的邻接矩阵。特别是，这个图应该有一个固定的度数（每个节点都连接到固定数量的节点 d）。

如果集合 d = N-1，则解决方案很简单：

A = ones(N) - eye(N);

我如何将它概括为任何 d？

添加：

这是一个解决方案（感谢 Oli Charlesworth）：

function A = fixedDegreeGraph(N, d)

A = zeros(N);

for i=1:N

    b = i;
    f = i;

    for k=1:floor(d/2)

        f = f + 1;
        if (f == N + 1)
            f = 1;
        end
        A(i, f) = 1;
        A(f, i) = 1;

        b = b - 1;
        if (b == 0)
            b = N;
        end
        A(i, b) = 1;
        A(b, i) = 1;

    end


end
4

1 回答 1

1

对于 even d，这是一种可视化方法的方法。

  • 画出排列成圆形的顶点。
  • 每个顶点都连接到它(d/2)的左手邻居，以及它(d/2)的右手邻居。

如何将其转换为邻接矩阵应该是相当明显的（提示：它将是一个循环矩阵，因此您可能会发现该toeplitz函数很有用）。

将其扩展到奇数d并不难......（尽管请注意，如果两者都是奇数，则没有解决方案Nd）

于 2013-03-02T12:26:19.060 回答