使用给定的度数以相等的概率创建所有强连通图

Question

我正在寻找一种方法,从节点和度数的所有强连接有向图(没有自循环)的空间均匀地采样.nk=(k_1,...,k_n), 1 <= k_i <= n-1

输入

• n,节点数量
• k = (k_1,...,k_n),其中k_i =进入节点的有向边数i(度数)

产量

• 具有n给定度数的节点(没有自循环)的强连接有向图,k_1,...,k_n其中每个可能的这样的图以相同的概率返回.

我特别感兴趣的n是大而k_i小的情况,因此简单地创建图形并检查强连通性是不可行的,因为概率基本上为零.

我浏览了各种各样的论文和方法,但找不到任何可以解决这个问题的方法.

Answer 1

继续创建随机路径，直到出现循环：

node1->node2->node3...->nodek->noder 其中 r<=k

现在，将循环noder->noder+1->nodek 替换为blob，我们将其称为blobr。现在继续将其连接到其余节点（以便节点不在该 blob 中）。每次你进入一个循环，就创建一个更大的斑点。

这最终将创建一个随机的最小强有向图。然后，添加随机边以满足传入条件。

这肯定会创建您的要求的所有组合。我认为所有组合的可能性都是相同的，但我必须考虑更多。

算法：这是一个粗略的方案。实际上，我在这里并没有重新解释图结构，也没有解决边缘条件，但这应该非常简单。

function randomStrongGraph(list<set<node>> chain, set<node> allnodes)
    Node newnode = random(allnodes - head(chain))
    alreadyEncountered = false
    for (i=0,i<chain.length-1;i++)
        if (newnode in chain(i))
            consolidate(chain, i)
            alreadyEncountered = true
            break
    if !alreadyEncountered
        chain.append(new set().add(newnode))    
    randomStrongGraph(chain, allnodes)