生成一个连接图并检查它是否有eulerian循环 [英] Generating a connected graph and checking if it has eulerian cycle

问题描述

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

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

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

在开始的时候，我打乱了第一个移动它的最后一个元素到空的元素。然后，在一个循环中，我在第一个数组的最后一个元素和第二个数组中的一个随机元素之间创建一条边，之后，将最后一个元素从第一个数组移动到另一个元素。

完成该部分后，我必须在顶点之间创建随机边，直到获得与我一样多的顶点需要。这又是非常简单的。我只是从 0 到 n - 1 范围内随机选择两个数字，如果这些顶点之间没有边缘，我创建一个。

这是代码：

  void generate（int n， double d）{
 initMatrix（n）; //<  - 创建一个邻接矩阵n x n，用0填充
 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--]; 
  - 存款; 
} 
 
 free（array1）; 
 free（array2）; 
 
 while（edges）{
 int a = rand（）％n; 
 int b = rand（）％n; 
 if（a == b || checkEdge（a，b））{
 continue; 
} 
 createEdge（a，b）; 
  - 存款; 
 
 
 
 
 
 
 $ b现在如果打印出来，图形。然后我想找到一个哈密尔顿循环。这部分工作。然后我遇到了我的祸根 - 欧拉循环。有什么问题？  
 
 
好吧，首先检查所有顶点是否均匀。而他们不是。总是。每一次，除非我选择生成完整的图表。 
 
 
 
我现在感觉被我自己的代码破坏了。有什么问题吗？还是应该是这样？我知道欧拉赛道很少见，但并不罕见。请帮助。
解决方案
让我们来分析euleran循环的概率，为了简单起见， 
 
 
给定一个图G的大小 n  n 顶点，无论边数如何。 / code>，选择一个任意的顶点。度数为偶数的概率大致为 1/2 （假设每个 u1，u2 ，<$ c $ （> v，u1）存在）= P（（v，u2）存在））。  
 
 
现在，从 G 删除 v ，然后创建一个新图 G'与 n-1 顶点，并且所有边都不连接到 v 。
 
 
 
类似地，对于 v' > G'  - 如果（v，v'）是 G' ，我们需要 d（v'）为奇数。否则，我们需要 d（v'）为偶数（均在 G'中）。无论哪种方式，它的概率仍然大致为〜1/2 。 （独立于以前的 v ）。  
 
 
 .... 
 
 
 
对于 i 第一轮，让＃（v）为到达当前连接到 v  。如果＃（v）为奇数，则其当前度数为奇数的概率为〜1/2 ，if ＃（v）是偶数，其当前度数为偶数的概率也是〜1/2 ，而我们保持当前概率〜1/2  
 
 
 
我们现在可以了解它的工作原理，并制定一个递推公式对于图是eulerian循环的概率：
 
 $ $ $ $ $ $ $ $ P> P（n）〜= 1/2 * P（n-1） 
 P（1）= 1 
  

这会给我们 P（n）〜= 2 ^ -n ，这对于合理的 n 是不太可能的。

---

请注意，1/2只是一个粗略的估计值（当 n->无穷大时是正确的） ，概率实际上有点高，但在 -n 中仍然是指数级的 - 这使得合理大小的图很不可能。

So, I wanted to have some fun with graphs and now it's driving me crazy.

First, I generate a connected graph with a given number of edges. This is the easy part, which became my curse. Basically, it works as intended, but the results I'm getting are quite bizarre (well, maybe they're not, and I'm the issue here). The algorithm for generating the graph is fairly simple.

I have two arrays, one of them is filled with numbers from 0 to n - 1, and the other is empty.

At the beginning I shuffle the first one move its last element to the empty one.

Then, in a loop, I'm creating an edge between the last element of the first array and a random element from the second one and after that I, again, move the last element from the first array to the other one.

After that part is done, I have to create random edges between the vertexes until I get as many as I need. This is, again, very easy. I just random two numbers in the range from 0 to n - 1 and if there is no edge between these vertexes, I create one.

This is the code:

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;
    }
}

Now, if I print it out, it's a fine graph. Then I want to find a Hammiltonian cycle. This part works. Then I get to my bane - Eulerian cycle. What's the problem?

Well, first I check if all vertexes are even. And they are not. Always. Every single time, unless I choose to generate a complete graph.

I now feel destroyed by my own code. Is something wrong? Or is it supposed to be like this? I knew that Eulerian circuits would be rare, but not that rare. Please, help.

解决方案

Let's analyze the probability for having euleran cycle, and for simplicity - let's do it for all graphs with n vertices, no matter number of edges.

Given a graph G of size n, choose one arbitrary vertex. The probability of it's degree being even is roughly 1/2 (assuming for each u1,u2, P((v,u1) exists) = P((v,u2) exists)).

Now, remove v from G, and create a new graph G' with n-1 vertices, and without all edges connected to v.

Similarly, for any arbitrary vertex v' in G' - if (v,v') was an edge on G', we need d(v') to be odd. Otherwise, we need d(v') to be even (both in G'). Either way, probability of it is still roughly ~1/2. (independent from previous degree of v).

....

For the ith round, let #(v) be the number of discarded edges until reaching the current graph that are connected to v. If #(v) is odd, the probability of its current degree being odd is ~1/2, and if #(v) is even, the probability of its current degree being even is also ~1/2, and we remain with current probability of ~1/2

We can now understand how it works, and make a recurrence formula for the probability of the graph being eulerian cyclic:

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

This is going to give us P(n) ~= 2^-n, which is very unlikely for reasonable n.

---

Note, 1/2 is just a rough estimation (and is correct when n->infinity), probability is in fact a bit higher, but it is still exponential in -n - which makes it very unlikely for reasonable size graphs.

这篇关于生成一个连接图并检查它是否有eulerian循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！