1

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.

Guy Coder
  • 24,501
  • 8
  • 71
  • 136
Maciej Zwierzchlewski
  • 19
  • 1
  • 1
  • 7
  • 3
    What's the size of the graph? The probability for each edge being even degree is roughly `2^-1`, which makes (again, roughly) `2^-n` for all vertices having even degree. For large values of `n`, you are going to need to create a LOT of graphs until you find one with eulerean cycle. – amit May 21 '15 at 08:43
  • If you just need to check for the *existence* of an Eulerian cycle in a connected graph, you only need to confirm that it has an even number of edges connected to each node. – r3mainer May 21 '15 at 08:56
  • @amit Well, I've been trying sizes ranged from 10 to 200. And, sadly, I do not think these are to be considered as very big graphs. – Maciej Zwierzchlewski May 21 '15 at 09:01
  • @ntzz1337 How many graphs of size 10 did you generate ? – vib May 21 '15 at 09:03
  • @ntzz1337 Since the probability is exponential in `-n` (number of vertices), it is very high. – amit May 21 '15 at 09:04
  • @amit Your answer made me think, I couldn't find a graph with all of its verticles being even from a group of `10000` graphs. I ran it with `100000` and I got `189` graphs having all their vertexes even. Still, none of them had an eulerian cycle, but that may be because of my eulerian cycle finding algorithm (or may not, I still have to investigate it further). But, it occurs that I was just expecting too good results. @vib This comment refers to graphs with 10 vertexes. – Maciej Zwierzchlewski May 21 '15 at 09:17
  • 1
    So you can see that the proba a graph is eulerian is about 0.00189 which is close to 2^{-n+1} = 0.00195. The reason why the asymptotic will be 2^(-n+1) and not 2^(-n) is that (roughly speaking) you have a global constraint so if the (n-1) first vertices have even degree, so does the last one... Appart from that @amit answer is great !! Also, connected + all vertices of even degree is a sufficient condition for Eulerian cycles so you may want to check you cycle finding algorithm – vib May 21 '15 at 09:26

1 Answers1

3

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.

amit
  • 175,853
  • 27
  • 231
  • 333