1

所以，我想用图表来找点乐子，现在它让我发疯了。

首先，我生成一个具有给定边数的连通图。这是容易的部分，这成了我的诅咒。基本上，它按预期工作，但我得到的结果非常奇怪（好吧，也许他们不是，我是这里的问题）。生成图的算法相当简单。

我有两个数组，其中一个填充了0to的数字n - 1，另一个是空的。

一开始，我将第一个元素打乱，将其最后一个元素移动到空元素。

然后，在一个循环中，我在第一个数组的最后一个元素和第二个数组的随机元素之间创建一条边，然后我再次将最后一个元素从第一个数组移动到另一个数组。

完成该部分后，我必须在顶点之间创建随机边，直到获得所需数量为止。同样，这非常容易。我只是在从0to范围内随机两个数字n - 1，如果这些顶点之间没有边，我创建一个。

这是代码：

void generate(int n, double d) {
    initMatrix(n); // <- creates an adjacency matrix n x n, filled with 0s
    int *array1 = malloc(n * sizeof(int));
    int *array2 = malloc(n * sizeof(int));
    int j = n - 1, k = 0;
    for (int i = 0; i < n; ++i) {
        array1[i] = i;
        array2[i] = 0;
    }

    shuffle(array1, 0, n); // <- Fisher-Yates shuffle
    array2[k++] = array1[j--];
    int edges = d * n * (n - 1) * .5;
    if (edges % 2) {
        ++edges;
    }
    while (j >= 0) {
        int r = rand() % k;
        createEdge(array1[j], array2[r]);
        array2[k++] = array1[j--];
        --edges;
    }

    free(array1);
    free(array2);

    while (edges) {
        int a = rand() % n;
        int b = rand() % n;
        if (a == b || checkEdge(a, b)) {
            continue;
        }
        createEdge(a, b);
        --edges;
    }
}

现在，如果我把它打印出来，这是一个很好的图表。然后我想找到一个汉密尔顿循环。这部分有效。然后我遇到了我的祸根——欧拉循环。有什么问题？

好吧，首先我检查所有顶点是否都是偶数。他们不是。总是。每一次，除非我选择生成一个完整的图表。

我现在感觉被我自己的代码摧毁了。有什么问题吗？或者它应该是这样的？我知道欧拉回路会很罕见，但并不那么罕见。请帮忙。

4

1 回答 1

3

让我们分析具有欧拉循环的概率，为简单起见 - 让我们对所有具有n顶点的图进行分析，无论边数如何。

给定一个大小为 的图 G n，选择一个任意顶点。其度数为偶数的概率大致1/2为（假设每个u1,u2, P((v,u1) exists) = P((v,u2) exists)）。

现在，从 中删除v，G并创建一个新图G'，其中有n-1顶点，并且所有边都没有连接到v。

类似地，对于- 如果是 上的边的任意顶点v'，我们需要是奇数。否则，我们需要是偶数（都在 中）。无论哪种方式，它的概率仍然是大致的。（独立于先前的程度）。G'(v,v')G'd(v')d(v')G'~1/2v

……

对于第ith 轮，设#(v)为连接到 的当前图之前丢弃的边数v。如果#(v)为奇数，则其当前度数为奇数的概率为 ，~1/2如果为偶数，则其当前度数为偶数#(v)的概率也为~1/2，我们保持当前概率为~1/2

我们现在可以理解它是如何工作的，并为图是欧拉循环的概率制定一个递归公式：

P(n) ~= 1/2*P(n-1)
P(1) = 1

这是要给我们P(n) ~= 2^-n的，这是不太可能的合理n。

请注意，1/2 只是一个粗略的估计（当 时是正确的n->infinity），概率实际上要高一些，但它仍然是指数级的-n——这使得它不太可能用于合理大小的图。

于 2015-05-21T08:58:31.490 回答