Combien de bords avant un graphique aléatoire est connecté?
-
04-11-2019 - |
Question
Soit $ g $ un graphique non dirigé avec $ n $ sommets et pas d'arêtes, et que $ f (k) $ soit la probabilité que si nous ajoutons des bords $ k $ au hasard à $ g $ que $ g $ sera connecté. Comment déterminer $ f (k) $ pour un $ n in in mathbb n $?
Détails:
Lorsque nous ajoutons un bord au graphique $ g $, tout bord qui peut exister serait également susceptible d'être ajouté. Nous ne pouvons pas ajouter le même bord deux fois, donc quand $ k = frac {n ^ 2 + n} 2 $ (le nombre de bords possibles dans un graphique avec $ n $ verticies), alors $ f (k) = 1 $ .
La définition de connecté peut être trouvée sur Wikipédia.
Pas de solution correcte
Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange