Répondre à la discussion
Affichage des résultats 1 à 6 sur 6

Besoin d'aide : graphes connexes, merci.



  1. #1
    DominoXIII

    Unhappy Besoin d'aide : graphes connexes, merci.


    ------

    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.

    -----

  2. Publicité
  3. 📣 Nouveau projet éditorial de Futura
    🔥🧠 Le Mag Futura est lancé, découvrez notre 1er magazine papier

    Une belle revue de plus de 200 pages et 4 dossiers scientifiques pour tout comprendre à la science qui fera le futur. Nous avons besoin de vous 🙏 pour nous aider à le lancer...

    👉 Je découvre le projet

    Quatre questions à explorer en 2022 :
    → Quels mystères nous cache encore la Lune 🌙 ?
    → Pourra-t-on bientôt tout guérir grâce aux gènes 👩‍⚕️?
    → Comment nourrir le monde sans le détruire 🌍 ?
    → L’intelligence artificielle peut-elle devenir vraiment intelligente 🤖 ?
  4. #2
    Denoby

    Re : Besoin d'aide : graphes connexes, merci.

    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

  5. #3
    DominoXIII

    Re : Besoin d'aide : graphes connexes, merci.

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

  6. #4
    acx01b

    Re : Besoin d'aide : graphes connexes, merci.

    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

  7. A voir en vidéo sur Futura
  8. #5
    invite986312212
    Invité

    Re : Besoin d'aide : graphes connexes, merci.

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

  9. #6
    DominoXIII

    Re : Besoin d'aide : graphes connexes, merci.

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

  10. Publicité

Discussions similaires

  1. équations ! besoin d'aide merci
    Par screur dans le forum Mathématiques du collège et du lycée
    Réponses: 2
    Dernier message: 24/09/2007, 20h28
  2. besoin d'aide merci
    Par stephanie74 dans le forum Internet - Réseau - Sécurité générale
    Réponses: 5
    Dernier message: 10/02/2007, 13h50
  3. Besoin D'aide, Merci
    Par SNAKE69 dans le forum Dépannage
    Réponses: 2
    Dernier message: 29/12/2005, 20h35
  4. besoin d'aide, merci
    Par malvi dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 13/11/2005, 23h48
  5. encore besoin d'aide, merci
    Par malvi dans le forum Mathématiques du supérieur
    Réponses: 7
    Dernier message: 13/11/2005, 19h39