algorithm - 以等概率创建具有给定入度的所有强连通图

Question

我正在寻找一种方法，从 n 的所有强连通有向图(无自环)的空间中均匀地采样。节点和入度 k=(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

现在，将循环 node->noder+1->nodek 替换为一个 blob，我们称它为 blobr。现在继续将它连接到剩余的节点(这样节点不在这个 blob 中)。每次你遇到一个循环，就创建一个更大的 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)