我试图找到一种优雅的算法来创建 1 和 0 的 N x N 矩阵，但有以下限制：
- 每行每列之和必须为Q（可自由选择）
- 对角线必须是 0
- 矩阵必须是对称的。
矩阵不一定是随机的（然而，随机和非随机解都很有趣），因此对于 Q 偶数，只需使每一行成为向量的循环移位
[0 1 1 0 ... 0 0 0 ... 0 1 1]（对于 Q=4）
是一个有效的解决方案。
然而，对于 Q odd 来说如何做到这一点呢？或者如何以随机的方式为 Q 做到这一点？
对于那些好奇的人，我正在尝试在抽象网络上测试一些现象。
如果之前已经回答过这个问题，我很抱歉，但我找到的所有问题都没有对称限制，这似乎使它变得更加复杂。我没有证据证明这样的矩阵总是存在，但我确实假设如此。
您尝试构造的对象更规范地称为无向 d 正则图（其中 d = Q）。根据握手定理，N 和 Q 不能同时为奇数。如果 Q 是偶数，则将顶点 v 连接到 v + k modulo N for k in {-Q/2, -Q/2 + 1, ..., -1, 1, ..., Q/2 - 1, Q/2}。如果 Q 是奇数，则 N 是偶数。像以前一样构造一个 (Q - 1)-正则图，然后添加从 v 到 v + N/2 modulo N 的连接。
如果你想要随机性，可以使用马尔可夫链，其极限分布在 d-正则图上是均匀的。您可以从任意 d 正则图开始。随机重复选取顶点 v、w、x、y。每当诱导子图看起来像
v----w
x----y ,
将其翻转到
v w
| |
x y .
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
