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

[inviteffe0e9ef]

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

[invite4793db90]

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.

[inviteffe0e9ef]

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 !

[inviteffe0e9ef]

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.

[A voir en vidéo sur Futura]

[invite6acfe16b]

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

[inviteffe0e9ef]

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

[invite6acfe16b]

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.

[inviteffe0e9ef]

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 !

[invite6acfe16b]

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.

[inviteffe0e9ef]

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

[invite79d10163]

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

[invite6acfe16b]

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.