Besoin d'aide : graphes connexes, merci.

[DominoXIII]

Dans le cadre de mon tipe voilà une question à laquelle j'ai dû répondre:
Soit G un graphe connexe à n sommets et k arrêtes et A un ensemble de p sommets de G.Soit G' le graphe dont les sommets sont A et les arrêtes, toute arrête de G dont les deux bouts sont dans A.

Combien y-a-t' il de distributions des arrêtes de G tel que G' est connexe?

Jusqu'à hier j'avais une belle formule qu'il m'avait pris un temps fou d'établir.Sauf que je viens de m'apercevoir qu'elle est fausse...

Je passe vraiment bientôt et cette formule est un élément centrale de ce que j'ai fait, si quelqu'un peut m'aider s'il vous plait!

Merci beaucoup.

Rmrq: la question formulée differement donne juste: si je tire un graphe connexe au hasard et que je prend p point de se graphe, quelle est la probabilité que ces p points forment un graphe connexe.

[Denoby]

Il n'y a pas de fonction générale dépendant de n et p, ça dépend du graphe.

Pour exemple, avec n=4 et k=3 et p=3
Si j'appelle a,b,c et d les sommets, je considère les 2 graphes suivants :
G d'arêtes ab, bc, et cd. (les 4 points forment une chaine)
G' d'arêtes ab,ac et ad. (le point a est relié au 3 autres)
Ces 2 graphes sont connexes
Il y a en tout C(4,3) (3 parmi 4) triplets de sommets distincts.

Parmi les triplets de sommets distincts de G, 2 forment un graphe connexe (abc et bcd). La proba de tomber sur un graphe connexe est donc 2/C(4,3)
Parmi les triplets de sommets distincts de G', 3 forment un graphe connexe (abc, acd et abd). La proba de tomber sur un graphe connexe est donc 3/C(4,3)

On trouve donc 2 graphes connexes à n sommets et k arêtes dont la proba de tomber sur un graphe connexe en tirant p sommets diffère.


On peut même généraliser l'exemple précédent à n et p quelconques (plus ou moins) et k=n-1 :
G le graphe à n sommets dont les arêtes forment une chaine (donc n--1 arêtes)
G' le graphe à n sommets dont l'un est relié à tous les autres (n-1 arêtes aussi)
On peut alors calculer qu'il y a n-(p-1) sous graphes de G connexes à p sommets et C(n-1,p-1) sous graphes de G' connexes à p sommets
Et en général n-(p-1) <> C(n-1,p-1).

Si on veut continuer la généralisation à d'autres couples (n,k), on peut s'amuser par exemple à rattacher un graphe complet (dans ce cas le calcul est facile, à voir pour d'autre graphes) au sommet en bout de branche de G, et au sommet de G' relié à tous les autres.

Denoby

[DominoXIII]

Exact , et merci pour cette demonstration qui m'a fait avancer la où je ne m'y attendai pas...Sauf justement la probabilité que je cherche prend en compte le graphe tiré au hasard...Par exemple si on devait tirer a 50/50 un des deux graphe que tu as cité, on aurait
P=proba 1er graphe*etre connexedans le 1e+proba 2e*etre connexe ds le 2e

ie P=1/2*2/C(4,3)+1/2*3/C(4,3)

J'avais pu calculer cette probabilité en faisant lune erreur stupide qui m'a permis de prouver que la probabilité de connexite de dependait pas du graphe justement...

[acx01b]

bonjour,

tu pourrais aussi faire un programme qui calcule cette probabilité pour n et p fixés en crééant des graphes et sous graphes au hasard

tu peux ensuite faire varier n et p et espérer une régularité dans la courbe ce qui te permettrait d'évaluer cette proba uniquement pour n = 2^a et p = 2^b

[invite986312212]

salut,

ça m'a l'air compliqué cette affaire! déjà, ta probabilité va dépendre de la distribution selon laquelle est engendré le graphe de départ G. Il y a une distribution "naturelle" sur l'ensemble des graphes connexes à n sommets: la loi uniforme, mais comment la simuler par exemple? tu peux aussi, les n sommets étant fixés, inclure ou non une arête pour chaque paire de sommets indépendamment et avec une probabilité p constante, puis ne retenir que les graphes connexes. Mais est-ce qu'il y a une valeur de p qui donne la loi uniforme sur les graphes connexes? ça me paraît douteux...

[DominoXIII]

Il y a un package graphe theory qui gere tout ca sous maple...Et pour le programme qui simulerait tout ça j'ai essayé...le problème est que gérer des graphes n'est pas chose simple et c'est lourd en ressource pour maple donc lent: environ 1 test tte les 2 secondes. Sauf que ma proba est tte petite(10e-6 au moins vu les resultats de simulations sur autre chose) et donc pour faire assez de resultats pour faire apparaitre tout ça...