我正在寻找一种方法,从节点和度数的所有强连接有向图(没有自循环)的空间均匀地采样.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小的情况,因此简单地创建图形并检查强连通性是不可行的,因为概率基本上为零.
我浏览了各种各样的论文和方法,但找不到任何可以解决这个问题的方法.
我已经使用Python多年了,但只是注意到一个非常令人困惑的事情.
a=[[]]*3
a[0].append(3)
和
a=[[] for i in range(3)]
a[0].append(3)
即使类型(列表)相同,也不会产生相同的效果.第一个产量a=[[3], [3], [3]],第二个产量a=[[3],[],[]](如预期的那样).
有人有解释吗？