Nous supposons que . Ensuite, le fait suivant est bien connu:
Je veux connaître les résultats sur le nombre de cycles hamiltoniens sur des graphes aléatoires.
Q1. Combien est le nombre attendu de cycles hamiltoniens sur ?
Q2. Quelle est la probabilité pour la probabilité de bord p sur ?
Réponses:
Comme l'a dit Yuval, Q1 est facile à répondre en utilisant la linéarité de l'attente (spoiler: ). Je ne connais pas la réponse exacte à Q2, mais elle pourrait être assez bonne si vous savez qu'elle est très faible: pour la plage de p où il y a au moins un cycle, elle soutient que P [ il y a plus d'un cycle | il y a au moins un cycle ] > 1 - 1 / n log n environ. En d'autres termes, une fois qu'il y a un cycle, il y en a plusieurs. La raison en est qu'une fois qu'il y a un cycle, il y a environ n 2(n−1)!pn p P[there is more than one cycle|there is at least one cycle]>1−1/nlogn n2 façons de créer un autre cycle à partir de celui-ci en échangeant deux bords du cycle par les deux bords "croisés" (c'est ce qu'on appelle un "2-flip" ou quelque chose dans certains de la littérature pertinente). Pour n'importe quelle paire d'arêtes, la chance que vous pouvez faire est . Donc, pour tous ces échecs, la chance est ( 1 - p 2 ) n 2 qui est à peu près e - ( p n ) 2 , ce qui est assez minuscule.p2 (1−p2)n2 e−(pn)2
la source