5

我试图找到一个优雅的算法来创建一个 1 和 0 的 N x N 矩阵，在限制下：

  • 每行和每列的总和必须为 Q（可以自由选择）
  • 对角线必须为 0
  • 矩阵必须是对称的。

矩阵不一定是随机的（但是，随机和非随机解都很有趣），所以对于 Q 偶数，只需使每一行成为向量的循环移位

[0 1 1 0 ... 0 0 0 ... 0 1 1]（对于 Q=4）

是一个有效的解决方案。

但是，如何为 Q 奇数做到这一点？或者如何以随机方式为 Q 做到这一点？

对于那些好奇的人，我正在尝试在抽象网络上测试一些现象。

如果之前已经回答过这个问题，我深表歉意，但我能找到的问题都没有对称限制，这似乎使它变得更加复杂。我没有证据证明这样的矩阵总是存在的，但我确实如此假设。

4

2 回答 2

6

您尝试构建的对象更规范地称为无向 d 正则图（其中 d = Q）。根据握手定理，N 和 Q 不可能都是奇数。如果 Q 是偶数，则将顶点 v 连接到 v + k 模 N 为 k 在 {-Q/2, -Q/2 + 1, ..., -1, 1, ..., Q/2 - 1,问/2}。如果 Q 是奇数，则 N 是偶数。像以前一样构造一个 (Q - 1)-正则图，然后添加从 v 到 v + N/2 模 N 的连接。

如果你想要随机性，有一个马尔可夫链，它的极限分布在 d 正则图上是均匀的。您从任何 d 正则图开始。反复随机选择顶点 v、w、x、y。每当诱导子图看起来像

v----w

x----y ,

翻转它

v    w
|    |
x    y .
于 2014-05-20T14:24:15.467 回答
1

如果可能，您也许可以始终遵循您的循环移位算法。

使用循环移位算法时需要遵循的唯一条件是保持第一行的对称性。

即保持 Q 1 在第一行，以便 Q[0,1] 到 Q[0,N-1] {假设 0 个索引行和列，Q[0,0] 为 0.} 是对称的，一个简单的例子是110010011。

因此，N = 10，Q = 5，您可以获得许多可能的安排，例如：

0 1 0 0 1 1 1 0 0 1 
1 0 1 0 0 1 1 1 0 0 
0 1 0 1 0 0 1 1 1 0 
0 0 1 0 1 0 0 1 1 1 
1 0 0 1 0 1 0 0 1 1 
1 1 0 0 1 0 1 0 0 1 
1 1 1 0 0 1 0 1 0 0 
0 1 1 1 0 0 1 0 1 0 
0 0 1 1 1 0 0 1 0 1 
1 0 0 1 1 1 0 0 1 0

或者

0 1 1 0 0 1 0 0 1 1 
1 0 1 1 0 0 1 0 0 1 
1 1 0 1 1 0 0 1 0 0 
0 1 1 0 1 1 0 0 1 0 
0 0 1 1 0 1 1 0 0 1 
1 0 0 1 1 0 1 1 0 0 
0 1 0 0 1 1 0 1 1 0 
0 0 1 0 0 1 1 0 1 1 
1 0 0 1 0 0 1 1 0 1 
1 1 0 0 1 0 0 1 1 0

但是正如您所看到的，对于奇数 N（这意味着偶数 N-1）和奇数 Q，不可能有任何这样的对称分布。. 希望它有所帮助。

于 2014-05-20T14:26:51.540 回答