有效枚举具有给定约束的所有可能矩阵

Question

背景

假设我们有一个M大小为n-by-的矩阵族n，它应该满足以下要求：

1. 矩阵的条目是0或1，即布尔值，但对角线条目始终是0s
2. 矩阵是对称的，即M == t(M)
3. 存在一个恒定的行（或等效的列）总和约束p，使得all(rowSums(M)==p) == TRUE

问题

• 特定的矩阵结构是否有任何潜在的特征，例如对称性、布尔值或其他特征，以便我们可以从中受益以提高搜索效率？
• 看来这个问题可以用图论的方式来解释。例如，该矩阵是n由入度和出度都等于 的顶点组成的图的邻接矩阵p。这可以通过 来完成sample_degseq，但我们可能必须找到它的所有同构映射。如果我们使用方法，我们该如何做到这一点igraph？

到目前为止，我的代码如下所示，但是当我们有更大的nor时，它会很慢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

Answer 1

问题归结为将度序列的所有实现生成为简单的无向图。igraph 目前包含以下相关工具：

• realize_degseq()创建一个单一的实现（我们想要所有）。
• sample_degseq()对实现进行随机抽样，并且它实现的一些方法可确保均匀抽样。
• is_graphical()测试是否存在任何实现。如果是这样，我们将度数序列称为图形化。这将是我们下面算法的基本构建块。

假设我们的度数序列是{2, 3, 1, 2}。我们可以这样画：

为了生成所有实现，我们需要以所有可能的方式连接存根。其中一些方法会导致多重边或自环，即非简单图。我们需要丢弃这些。

有效生成所有简单实现的技巧是尽早检测我们是否被迫创建一个非简单图并停止。我们可以按如下方式执行此操作。让我们采用第一个顶点，它有d_1 = 2存根。我们可以将这n-1 = 3两个存根连接到其他顶点。有多种(n-1) \choose d_1 = 3 \choose 2 = 3方法可以做到这一点，即以下几种：

我们可以从这三种配置中得到一个简单的图表吗？请注意，在连接顶点 1 的所有存根之后，剩下的是顶点 2、3、4 的度数序列，它可能是也可能不是图形的。我们称之为降阶序列。对于这三种情况，我们有：

2 0 2
2 1 1
3 0 1

（丢弃第一个度数现在变为0的顶点，不再需要考虑。）

其中只有第二个是图形化的，因此我们只需沿着这条路径继续构建即可。

> is_graphical(c(2,0,2))
[1] FALSE
> is_graphical(c(2,1,1))
[1] TRUE
> is_graphical(c(3,0,1))
[1] FALSE

然后取第二个剩余度数序列，我们可以以相同的方式递归地继续构造，获得起始度数序列的单一可能实现：

用伪代码表达这个递归结构：

# degrees is a vector of degrees
# vertices is a vector of corresponding vertex names
# generate(degrees, vertices) returns all realizations 
# of the given degrees as simple graphs
generate(degrees, vertices):
    RESULT = {} # empty list
    d1 = degrees[1]  # first degree
    v1 = vertices[1] # first vertex
    drest = degrees[2:]  # rest of degrees
    vrest = vertices[2:] # rest of vertices
    for each size d1 subset S of vrest:
        dreduced = drest
        dreduced[S] -= 1 # decrement by one elements in S to obtain the reduced degree sequence
        if is_graphical(dreduced):
            for each graph in generate(dreduced, vrest),
            add vertex v1 to it and connect it to each of S,
            then append the graph to RESULT
    return RESULT

我在 Mathematica 中有一个实现，但我对 R 不够流利，无法花时间用该语言实现它。

我应该指出，有更有效的方法来进行枚举，但它们有点复杂。在这里，我们采用第一个顶点，并以所有可能的方式将其所有存根连接到其余顶点。然后，在这些可能性中，我们只考虑可行的可能性，即那些导致图形降度序列的可能性。可以仅获取第一个顶点的单个存根，将其连接起来，然后就可以确定继续是否可行。这可以使用本文中的星形约束图性定理来完成。