生成具有均匀概率(或更小)的随机立方图

概述虽然这可能看起来像作业,我向你保证不是.不过,这源于我做过的一些功课. 如果每个顶点的度数只有三个,我们来调用一个没有自边缘的无方向图.给定一个正整数N我想在N个顶点上生成一个随机立方图.我希望它具有统一的概率,也就是说,如果在N个顶点上有M个三次曲线,则生成每一个的概率为1 / M.一个较弱的条件仍然很好,每个立方图都有非零概率. 我觉得有一个快速和聪明的方式来做到这一点,但到目前为止,我一直没 虽然这可能看起来像作业,我向你保证不是.不过,这源于我做过的一些功课.

如果每个顶点的度数只有三个,我们来调用一个没有自边缘的无方向图.给定一个正整数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,因此算法可能不会终止.此外,我并不完全相信概率是统一的.

我的代码可能有很多改进,但是你可以建议一个更好的算法来实现？

解决方法 假设N是偶数. (否则在N个顶点上不能有一个立方图).

您可以执行以下 *** 作：

取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.

总结

以上是内存溢出为你收集整理的生成具有均匀概率(或更小)的随机立方图全部内容，希望文章能够帮你解决生成具有均匀概率(或更小)的随机立方图所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。