Create a linked graph and check if it has an eulerian cycle

Question

So, I wanted to have fun with the graphs, and now it drives me crazy.

First, I create a connected graph with a given number of edges. This is the easy part that has become my scourge. Basically, it works as intended, but the results that I get are rather strange (well, maybe that’s not the case, and I have a problem here). The graph generation algorithm is quite simple.

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

First, I shuffle the first one, translating its last element into an empty one.

Then in the loop, I create an edge between the last element of the first array and the random element from the second, and after that I again move the last element from the first array to another.

After this part, I have to create random edges between the vertices until I get as much as I need. This, again, is very easy. I just arbitrarily two numbers ranging from 0to n - 1, and if there is no edge between these vertices, 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, this is a great schedule. Then I want to find the Hamiltonian cycle. This part works. Then I get to my curse - the Eulerian cycle. What is the problem?

Well, first I will check if all the vertices are even. And this is not so. Is always. Every time if I do not want to generate a full schedule.

Now I feel ruined by my own code. Something is wrong? Or should it be so? I knew that Euler schemes would be rare, but not so rare. Please, help.

Answer 1

, - 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/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 - .