Complexité algo recherche degré de connexité...
Répondre à la discussion
Affichage des résultats 1 à 30 sur 46

Complexité algo recherche degré de connexité...



Vue hybride

  1. #1
    inviteffe0e9ef

    Complexité algo recherche degré de connexité...

    Bonjour à tous !

    Voila... Je suis en L3 info, et nous avons eu des rattrapages en maths. Parmi ces rattrapages figurait un cour de maths sur les graphes. A un moment, le professeur nous a parlé d'un problème qui m'a fortement interessé:

    Comment determiner le minimum des points a supprimer dans un graphe connexe pour que celui ne le soit plus ?

    Il a ajouté que c'était un problème très complexe au sens algorithmique et que rien n'avait été trouvé qui soit rapide.

    Avec mon culot d'éléphant , je me suis dit bon... On va trouver un algorithme alors... Et j'ai trouvé, preuve à l'appui.

    Il y a donc maintenant deux possibilités:
    1. - Je me suis trompé...
    2. - Ce n'est pas un problème compliqué...

    Pour le 1), j'ai vérifié et revérifié (je ne demande à personne de vérifier), ça fonctionne théoriquement.
    Mais c'est le 2. qui m'amène a vous demander si vous connaitriez le meilleur algorithme qui fasse ceci en un temps optimal ?...

    Merci à celui qui m'aidera parce que je ne trouve rien sur Internet...

  2. #2
    invite4793db90

    Re : Complexité algo recherche degré de connexité...

    Salut,

    je ne saurais pas répondre à ta question, mais as-tu aussi considéré les graphes en dimension quelconque ? (Un maillage du tore ou plus généralement d'une surface de genre p par exemple.)

    Cordialement.

  3. #3
    inviteffe0e9ef

    Re : Complexité algo recherche degré de connexité...

    Tous les graphes sont adaptés à mon algorithme, et la preuve n'utilise aucune contrainte.

    Mais cependant, si tu as un graphe à me faire tester (pas trop gros parce que sinon à la main, j'en aurai pour longtemps !), je suis particulièrement ouvert !

  4. #4
    inviteffe0e9ef

    Re : Complexité algo recherche degré de connexité...

    Ca y est, il semblerait que j'ai trouvé...
    Je crois que c'est le même problème que de trouver la fiabilité d'un réseau...

    et les amis... C'est un problème NP-Complet...
    que je le résous en temps polynomial si mes calculs sont bons.
    Ca, c'est très sympa ...


    http://en.wikipedia.org/wiki/List_of...plete_problems
    Section Network design->Cuts and connectivity->Network reliability

    Ne nous réjouissons pas trop vite... Je vais encore vérifier tout.

  5. A voir en vidéo sur Futura
  6. #5
    invite6acfe16b

    Re : Complexité algo recherche degré de connexité...

    Citation Envoyé par djar Voir le message
    C'est un problème NP-Complet...Ne nous réjouissons pas trop vite... Je vais encore vérifier tout.
    Je crois que tu fais bien de tout vérifier. Ce n'est pas que je remette en question tes capacités, mais cela m'est aussi arrivé de croire que j'avais trouvé cela. Il m'a suffit de discuter avec mon collègue pour me faire démonter en 30 secondes...

  7. #6
    inviteffe0e9ef

    Re : Complexité algo recherche degré de connexité...

    Tu comprendras que je ne veuille pas donner l'algo tout de suite...

    Mais faisons un test ! Donne moi un graphe fortement connexe et je te dirais quels points supprimer pour le rendre non connexe le plus rapidement... Le problème, c'est que j'ai pas encore programmé l'algo sur ordi donc je suis obligé de le faire à la main: je risque de faire des erreurs de calcul, mais je ferais attention...

  8. #7
    invite6acfe16b

    Re : Complexité algo recherche degré de connexité...

    Citation Envoyé par djar Voir le message
    Tu comprendras que je ne veuille pas donner l'algo tout de suite...

    Mais faisons un test ! Donne moi un graphe fortement connexe et je te dirais quels points supprimer pour le rendre non connexe le plus rapidement... Le problème, c'est que j'ai pas encore programmé l'algo sur ordi donc je suis obligé de le faire à la main: je risque de faire des erreurs de calcul, mais je ferais attention...
    Jusqu'à combien de sommets veux-tu aller ?

    Si tu me dis n, je te concocterai un autre graphe de taille n+1 et on regardera comment varie le temps de calcul.

  9. #8
    inviteffe0e9ef

    Re : Complexité algo recherche degré de connexité...

    Je suis vraiment tenté de te dire n, mais j'ai pas encore programmer l'algo et j'ai des partiels à préparer ! Mais disons n = 10 pour commencer (et c'est déjà grand) puis n=11, je ne tricherais pas et je te dirais le temps que j'ai mis à la main... Qui risque d'être grand ! Mais si déjà je met moins de quinze minutes à la main, ça veut dire que ça devrait prendre quelques millieme de secondes sur un ordinateur classique...

    Je ferais tout mon possible pour te faire l'algo sur ordi en deux semaines, comme ça on verra le temps réel ! Et on pourra tester avec n=1000 et n=1001 !

    Merci de m'aider en tout cas !

  10. #9
    invite6acfe16b

    Re : Complexité algo recherche degré de connexité...

    Ok,

    je vais te donner un graphe de 10 sommets bientôt. Mais comme je n'ai pas non plus trop de temps, je te prie de m'excuser si cela attends ce soir. Ceci dit, je ne connais pas bien le problème et je ne sais pas quel graphe sont difficiles pour ce problème. Je vais donc certainement te donner un graphe aléatoire de densité 1/2.

  11. #10
    inviteffe0e9ef

    Re : Complexité algo recherche degré de connexité...

    okidok', mais le probleme, je te l'avoue, c'est que si tu génére un graphe aléatoire, tu risques d'avoir du mal à vérifier la réponse que je vais te donner...

  12. #11
    invite79d10163

    Re : Complexité algo recherche degré de connexité...

    Effectivement c'est un probleme interressant.

    Il existe plusieurs familles d'algorithmes qui résolvent ce probleme. Pour résumer il y a deux grandes familles :
    - les algorithmes à base de flot. pâr éxemple la recherche des coupes minimales entre chaque paire de noeud d'un graphe
    - les algorithmes dits aléatoires, qui malgré leurs noms fournissent des résultats exacts. exemple marche aléatoire sur un graphe...

    Je n'en connais pas la complexité algorithmique....

  13. #12
    invite6acfe16b

    Re : Complexité algo recherche degré de connexité...

    Citation Envoyé par djar Voir le message
    okidok', mais le probleme, je te l'avoue, c'est que si tu génére un graphe aléatoire, tu risques d'avoir du mal à vérifier la réponse que je vais te donner...
    Tu as raison, je vais te préparer un graphe ce soir pour lequel je connais la réponse.
    Mais peut-être qu'en faisant cela, je vais rendre le problème plus simple qu'il ne l'est. Mais bon, au cas où, on fera plusieurs essais.

Discussions similaires

  1. besoin d'aide a propos d'un petit algo
    Par invite9f37bb98 dans le forum Logiciel - Software - Open Source
    Réponses: 16
    Dernier message: 02/09/2007, 17h17
  2. Chercher Algo
    Par invite717d01ee dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 15/03/2007, 17h24
  3. transformée de Fourier (algo numérique)
    Par Heimdall dans le forum Mathématiques du supérieur
    Réponses: 8
    Dernier message: 07/03/2007, 04h52
  4. Retrouver algo à partir de résultats
    Par invite57362939 dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 26/02/2007, 20h30
  5. Graphes:lien entre connexite et degre
    Par invitef55e92ca dans le forum Mathématiques du supérieur
    Réponses: 6
    Dernier message: 25/02/2006, 16h22