Générer un graphe connecté et vérifier s’il a un cycle eulérien

Alors, je voulais m’amuser avec les graphiques et maintenant, ça me rend folle.

Tout d’abord, je génère un graphe connecté avec un nombre donné d’arêtes. C’est la partie facile, qui est devenue ma malédiction. Fondamentalement, cela fonctionne comme prévu, mais les résultats que j’obtiens sont assez bizarres (enfin, peut-être que ce n’est pas le cas, et je suis l’enjeu ici). L’algorithme pour générer le graphique est assez simple.

J’ai deux tableaux, l’un est rempli de nombres de 0 à n - 1 et l’autre est vide.

Au début, je mélange le premier et déplace son dernier élément vers le vide.

Ensuite, dans une boucle, je crée une arête entre le dernier élément du premier tableau et un élément aléatoire du deuxième puis, après cela, je déplace à nouveau le dernier élément du premier tableau vers l’autre.

Une fois cette partie terminée, je dois créer des arêtes aléatoires entre les sumts jusqu’à en obtenir autant que nécessaire. C’est encore très facile. Je viens juste aléatoire deux nombres dans la gamme de 0 à n - 1 et s’il n’y a pas de bord entre ces sumts, j’en crée un.

C’est le code:

 void generate(int n, double d) { initMasortingx(n); // <- creates an adjacency matrix nxn, 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); // = 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; } } 

Maintenant, si je l’imprime, c’est un bon graphique. Ensuite, je veux trouver un cycle hammiltonien. Cette partie fonctionne. J’arrive ensuite à mon fléau – cycle eulérien. Quel est le problème?

Eh bien, je vérifie d’abord si tous les sumts sont pairs. Et ils ne sont pas. Toujours. Chaque fois, sauf si je choisis de générer un graphique complet.

Je me sens maintenant détruit par mon propre code. Quelque chose ne va pas? Ou est-ce censé être comme ça? Je savais que les circuits eulériens seraient rares, mais pas si rares. S’il vous plaît, aidez.

Analysons la probabilité d’avoir un cycle eulérien et de simplifier les choses. Faisons-le pour tous les graphiques à n sumts, quel que soit le nombre d’arêtes.

Étant donné un graphe G de taille n , choisissez un sumt arbitraire. La probabilité que son degré soit pair est d’environ 1/2 (en supposant que pour chaque u1,u2 , P((v,u1) exists) = P((v,u2) exists) ).

Supprimez maintenant v de G et créez un nouveau graphe G' avec n-1 sumts et sans que toutes les arêtes soient connectées à v .

De même, pour tout sumt arbitraire v' dans G' – si (v,v') était un bord sur G' , il faut que d(v') soit impair. Sinon, il faut que d(v') soit pair (les deux en G' ). Quoi qu’il en soit, la probabilité que cela soit encore d’environ ~1/2 . (indépendant du degré précédent de v ).

….

Pour le ième tour, prenons #(v) le nombre d’arêtes ignorées jusqu’à atteindre le graphique actuel connecté à v . Si #(v) est impair, la probabilité que son degré actuel soit impair est de ~1/2 et si #(v) est pair, la probabilité que son degré actuel soit pair est également de ~1/2 , et nous restons avec probabilité actuelle de ~1/2

Nous pouvons maintenant comprendre comment cela fonctionne et créer une formule de récurrence pour la probabilité que le graphe soit euclien cyclique:

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

Cela va nous donner P(n) ~= 2^-n , ce qui est très peu probable pour n raisonnable.


Notez que 1/2 est juste une estimation approximative (et est correcte lorsque n->infinity ), la probabilité est en fait un peu plus élevée, mais elle est toujours exponentielle dans -n – ce qui rend très improbable des graphes de taille raisonnable.