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

Question

虽然这可能看起来像家庭作业,但我向你保证不是.这源于我做过的一些家庭作业.

如果每个顶点的度数恰好为3,那么让我们调用一个没有自我边缘"立方"的无向图.给定正整数N我想在N个顶点上生成随机立方图.我希望它具有统一的概率,也就是说,如果N个顶点上有M个立方图,则生成每个顶点的概率为1/M. 一个较弱的条件仍然很好,每个立方图具有非零概率.

我觉得有一个快速而聪明的方法来做到这一点,但到目前为止,我一直没有成功.

我是一个糟糕的程序员,请忍受这个糟糕的代码:

PRE:edges =(3*个节点)/ 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级.因此算法可能不会终止.而且,我并不完全相信概率是一致的.

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

Answer 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)),(j,C(j))}的组.

这给了我们3N有序对.我们将它们配对:(u,v)与(v,u)配对.

因此,任何立方图对应于配对,反之亦然......

有关此算法和更快算法的更多信息,请参见:快速生成随机正则图.