如果每个顶点的度数只有三个,我们来调用一个没有自边缘的无方向图.给定一个正整数N我想在N个顶点上生成一个随机立方图.我希望它具有统一的概率,也就是说,如果在N个顶点上有M个三次曲线,则生成每一个的概率为1 / M.一个较弱的条件仍然很好,每个立方图都有非零概率.
我觉得有一个快速和聪明的方式来做到这一点,但到目前为止,我一直没有成功.
我是一个坏的编码器,请承担这个可怕的代码：
PRE：edges =(3 * nodes)/ 2,节点为偶数,常数以散列的方式进行选择(BIG_PRIME大于边,SMALL_PRIME大于节点,LOAD_FACTOR较小).
void random_cubic_graph() {
int i,j,k,count;
int *degree;
char guard;
count = 0;
degree = (int*) calloc(nodes,sizeof(int));
while (count < edges) {
/* Try a new edge at random */
guard = 0;
i = rand() % nodes;
j = rand() % nodes;
/* Checks if it is a self-edge */
if (i == j)
guard = 1;
/* Checks that the degrees are 3 or less */
if (degree[i] > 2 || degree[j] > 2)
guard = 1;
/* Checks that the edge was not already selected with an hash */
k = 0;
while(A[(j + k*BIG_PRIME) % (LOAD_FACTOR*edges)] != 0) {
if (A[(j + k*BIG_PRIME) % (LOAD_FACTOR*edges)] % SMALL_PRIME == j)
if ((A[(j + k*BIG_PRIME) % (LOAD_FACTOR*edges)] - j) / SMALL_PRIME == i)
guard = 1;
k++;
}
if (guard == 0)
A[(j + k*BIG_PRIME) % (LOAD_FACTOR*edges)] = hash(i,j);
k = 0;
while(A[(i + k*BIG_PRIME) % (LOAD_FACTOR*edges)] != 0) {
if (A[(i + k*BIG_PRIME) % (LOAD_FACTOR*edges)] % SMALL_PRIME == i)
if ((A[(i + k*BIG_PRIME) % (LOAD_FACTOR*edges)] - i) / SMALL_PRIME == j)
guard = 1;
k++;
}
if (guard == 0)
A[(i + k*BIG_PRIME) % (LOAD_FACTOR*edges)] = hash(j,i);
/* If all checks were passed,increment the count,print the edge,increment the degrees. */
if (guard == 0) {
count++;
printf("%d\t%d\n",i,j);
degree[i]++;
degree[j]++;
}
}
问题是它必须被选中的最后一个边缘可能是一个自我边缘.当N-1个顶点已经具有3级时,只有1个具有度数1,因此算法可能不会终止.此外,我并不完全相信概率是统一的.
我的代码可能有很多改进,但是你可以建议一个更好的算法来实现？
解决方法
您可以执行以下操作：
取3N点,分成N组,每组3个.
现在将这3N点随机配对(注意：3N是偶数).即随机结婚两次,形成3N / 2婚姻).
如果组i和组j之间存在配对,则在i和j之间创建一个边.这给出了N个顶点的图.
如果这个随机配对没有创建任何多个边或循环,那么你有一个三次图.
如果不再试这在预期的线性时间运行并产生均匀分布.
注意：N顶点上的所有三维图都是通过这种方法生成的(响应Hamish的注释).
看到这个：
令G为N个顶点的立方图.
让顶点为1,2,… N.
让j的三个邻居为A(j),B(j)和C(j).
对于每个j,构造有序对组{(j,A(j)),(j,B(j)),C(j))}.
这给我们3N有序对.我们配对：(u,v)与(v,u)配对.
因此,任何三次图对应于配对,反之亦然
有关此算法的更多信息和更快的算法可以在这里找到：Generating Random Regular Graphs Quickly.
