高效枚举满足约束的n阶布尔对称矩阵及igraph实现技术问询

我们要寻找满足以下条件的n×n矩阵M：

• 元素为0或1（布尔型），且对角线元素恒为0；
• 矩阵对称，即M == t(M)；
• 所有行（列）的和均等于定值p，也就是all(rowSums(M)==p) == TRUE。

1. 能否利用矩阵的特殊结构（如对称性、布尔型等）提升枚举搜索的效率？
2. 该问题可转化为图论问题：矩阵是n个顶点、每个顶点度数为p的图的邻接矩阵。可通过sample_degseq生成相关图，但要找出所有非同构的图，用igraph该如何操作？

当前代码在n或p较大时运行缓慢，且无法确定是否遗漏了符合条件的矩阵：

f <- function(n, p) {
    # helper function to check if requirement holds
    checker <- function(M, p, i = nrow(M) - 1) {
        rs <- rowSums(M)
        if ((i == nrow(M) - 1)) {
            return(all(rs == p))
        } else {
            return(all(rs[1:i] == p) && all(rs[-(1:i)] <= p))
        }
    }

    # start from all-0's matrix
    lst <- list(matrix(0, n, n))
    for (i in 1:(n - 1)) {
        js <- (i + 1):n
        r <- list()
        for (mat in lst) {
            k <- p - sum(mat[i, ])
            if (k == 0) {
                if (checker(mat, p, i)) {
                    r <- c(r, list(mat))
                }
            }
            if (k > 0 && length(js) >= k) {
                idx <- combn(length(js), k, \(v) js[v], simplify = FALSE)
                for (u in idx) {
                    mm <- mat
                    mm[i, u] <- 1
                    mm[u, i] <- 1
                    if (checker(mm, p, i)) {
                        r <- c(r, list(mm))
                    }
                }
            }
        }
        lst <- r
    }
    lst
}

• 当n <- 4且p <- 2时，可得到3个矩阵：

[[1]]
     [,1] [,2] [,3] [,4]
[1,]    0    1    1    0
[2,]    1    0    0    1
[3,]    1    0    0    1
[4,]    0    1    1    0

[[2]]
     [,1] [,2] [,3] [,4]
[1,]    0    1    0    1
[2,]    1    0    1    0
[3,]    0    1    0    1
[4,]    1    0    1    0

[[3]]
     [,1] [,2] [,3] [,4]
[1,]    0    0    1    1
[2,]    0    0    1    1
[3,]    1    1    0    0
[4,]    1    1    0    0

• 当n <- 3且p <- 2时，仅能得到1个矩阵：

[[1]]
     [,1] [,2] [,3]
[1,]    0    1    1
[2,]    1    0    1
[3,]    1    1    0

1. 利用矩阵结构提升枚举效率的方法 #

对称性剪枝 #

由于矩阵对称，只需处理上三角（或下三角）区域，设置M[i,j]（i<j）时自动同步M[j,i]，将需枚举的元素数量从n(n-1)减少到n(n-1)/2，直接减半计算量。

提前约束行和余量 #

构建矩阵时，除确保当前行和为p，还要严格检查后续行的剩余可分配1的数量：

• 处理第i行时，后续第k行（k>i）已有的1的数量为s，则剩余未处理的列中必须至少有(p-s)个位置可放置1，否则直接剪枝该分支，无需继续枚举。

同构剪枝避免重复 #

枚举过程中记录已生成矩阵的规范形式（如按行排序后的矩阵，或对应图的规范标签），若新生成矩阵的规范形式已存在，则跳过该矩阵，减少重复计算。

布尔运算优化 #

用整数向量替代矩阵存储，每行用二进制数表示，行和计算、元素设置均可通过位运算完成，比传统矩阵操作效率更高。在R中可借助bit64包处理大整数，或用整数向量模拟二进制位。

2. 用igraph处理非同构正则图枚举 #

该问题本质是枚举所有n个顶点的p-正则非同构图，可通过以下步骤实现：

直接生成非同构正则图 #

推荐使用R包graphclasses（封装了nauty工具的功能），可直接生成所有非同构的正则图：

library(graphclasses)
# 生成所有n个顶点的p-正则非同构图
graphs <- regular.graphs(n, p)
# 转换为邻接矩阵
matrices <- lapply(graphs, function(g) as.matrix(g[]))

手动去重（针对sample_degseq生成的图） #

若用sample_degseq批量生成图，需通过同构判断去重：

• 对两个图g1、g2，用igraph::is_isomorphic(g1, g2)判断是否同构；
• 维护一个图列表，每次生成新图后，检查是否与列表中已有图同构，不同构才加入列表。但该方法在n和p较大时效率较低，因为同构判断开销大。

前置检查 #

生成前需确认度数序列可图：n*p必须为偶数（正则图总度数为偶数），且p < n（每个顶点不能自连，也无法连接所有其他顶点除非p=n-1）。

内容的提问来源于stack exchange，提问作者ThomasIsCoding