生成连通图并检查它是否有欧拉循环

Question

所以，我想从图表中获得一些乐趣，现在它让我发疯了。

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

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

一开始我打乱第一个，把它的最后一个元素移到空的。

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

完成该部分后，我必须在顶点之间创建随机边，直到获得所需数量为止。同样，这非常容易。我只是在 0 到 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;
    }
}

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

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

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

Answer 1

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

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

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

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

.....

对于第 i 轮，设 #(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 中仍然是指数 - 这使得它对于合理大小的图表来说非常不可能。

生成连通图并检查它是否有欧拉循环

Generating a connected graph and checking if it has eulerian cycle

c

algorithm

graph

chinese-postman