生成 n 维超立方体的距离矩阵

Question

是否有任何算法或方法可以生成任意维度的超立方体的邻接矩阵？假设你的输入是 5，它将创建一个 5 维超立方体

我能找到的都是来自 维基

和 沃尔夫拉姆

Answer 1

如果你想生成一个N维单位超立方体的顶点，你基本上可以制作一个N值真值表。这是我使用的一些代码：

function output = ttable(values)

  output = feval(@(y)feval(@(x)mod(ceil(repmat((1:x(1))', 1, numel(x) - 1) ./ repmat(x(2:end), x(1), 1)) - 1, repmat(fliplr(y), x(1), 1)) + 1, fliplr([1 cumprod(y)])), fliplr(values));
end

要获取 5 维超立方体的顶点，您可以这样称呼它：

vertices = ttable(ones(1, 5) * 2) - 1;

从这里您可以通过查找仅相差一位的所有顶点来计算邻接矩阵，即：

adj_list = zeros(2^5, 5);
adj_mat = zeros(2^5, 2^5);
for v=1:2^5
  L1_dists = sum(abs(vertices - repmat(vertices(v, :), 2^5, 1)), 2);
  adj_list(v, :) = find(L1_dists == 1);
  adj_mat(v, find(L1_dists == 1)) = 1;
end

Answer 2

我知道这有点晚了，但该解决方案与其他帖子不同并且基于递归，所以希望有人会发现它有用。

首先，我们将尝试建立一些关于如何从 (N-1) 立方体构建 N 立方体的直觉。 当您想到 1 立方体时，它只是一条线段。为了得到一个 2 立方体（正方形），我们复制线段，平移它，并沿着平移路径添加边。 类似地，为了得到一个 3 立方体，我们获取该正方形，复制它，平移它，然后连接边。 如果您很难想象这一点，请考虑下图：

现在，如果有一些数学机器可以做到这一点就好了！ 好吧，我们很幸运，因为他们是：克罗内克产品。 本质上，它为我们提供了一种复制邻接矩阵的方法，然后只需将结果粘合在一起即可。 粘合是通过将上图中的虚线添加为低维立方体的两个副本的邻接矩阵中的附加边来完成的。 以图片形式（因为这个异教徒网站不支持 LaTeX）： 就是这样！任意维度的超立方体的邻接矩阵。 最后一个警告：这些矩阵呈指数增长，并且大部分都用零填充（每个节点仅连接到 2^N 个其他节点中的 N 个），因此稀疏矩阵是必须的。这是一个快速实施。享受吧！

function A = hypercube(N)
  if N==1
    A = sparse([0 1;1 0]);
  else
    A = kron(sparse(eye(2)),hypercube(N-1)) + ...
         kron(sparse([0 1;1 0]),diag(sparse(ones(1,2^(N-1)))));
  end
end