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

[martini_bird]

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]

[Sylvestre]

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

[Sylvestre]

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 !

[Sylvestre]

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

[inviteffe0e9ef]

Interessant, je vais chercher des infos dans cette direction...

Mon algorithme est déterministe.
J'ai pas internet chez moi, mais seulement à la fac donc demain soir , je testerais le programme et après demain, je vous filerais les résultats...

[Sylvestre]

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.

[Sylvestre]

Essaie avec ça :

2-8
2-10
2-4
8-10
8-1
4-10
1-4
8-5
8-7
7-1
1-5
3-7
3-6
5-6
9-5
9-6

[invite79d10163]

Pour trouver des algos , tu peux chercher "vertex connectivity"

Un petit détail, pour graphe complet (c'est à dire qur tout les sommets du graphe sont liés à tout les autres), il faudrait enlever tout les sommets pour le rendre non-connexe. C'est le genre de points particuliers que tu peux tester avec ton algorithme.

[inviteffe0e9ef]

Comme je n'ai pas Internet chez moi, je resous les cas avec du retard... Je vais tester le tiens ce soir !

Mais hier, j'etais trop impatient donc j'ai code mon algo. 2h apres, je fesais un test avec 13 vertices. Resultat tres remarquable: 15ms en moyenne et parfois, c'est mon chronometre qui n'etait pas assez precis et qui m'affichait 0ms !! J'ai donc suivi ce que tu m'as dit de faire: augmenter de 1 le nombre de vertices. Resultat avec 14 vertices: toujours 15ms, le chronometre n'est pas assez precis car la difference est inferieur a 1ms !!! C'est plutot bien je pense...
J'ai jamais fait un algo aussi puissant !

A bientot !

[Sylvestre]

Ok,

dans ce cas, il va falloir faire des tests avec plus de sommets, genre 50, et regarder le comportement du temps de calcul.
Si c'est vraiment polynomial, alors tu es millionnaire !
(désolé, mais j'ai encore des doutes, cela semble trop beau)

[inviteffe0e9ef]

En fait, j'ai transforme la complexite temporelle en complexite spatiale, meme si cela reste faisable du fait de l'utilisation de deux petites astuces mathematiques que je ne dirais pas (tout de suite)...

Je teste ton graphe et ensuite on verra avec 50 points !
Note: normalement, je dis bien normalement, 50 points et 51 points ne devrait pas trop deranger mon algo... Si mes calculs sont bons...

C'est tellement interessant !!!

[Sylvestre]

En fait, j'ai transforme la complexite temporelle en complexite spatiale, meme si cela reste faisable du fait de l'utilisation de deux petites astuces mathematiques que je ne dirais pas (tout de suite)...

Je teste ton graphe et ensuite on verra avec 50 points !
Note: normalement, je dis bien normalement, 50 points et 51 points ne devrait pas trop deranger mon algo... Si mes calculs sont bons...

C'est tellement interessant !!!

Je me demande : Combien de temps met ton algorithme pour donner la réponse si je te donne une clique à n sommets ?

[invite986312212]

Si c'est vraiment polynomial, alors tu es millionnaire !

je ne connais pas bien cette question de P=NP mais si j'ai bien compris, si c'est vrai pour un problème, c'est vrai pour tous ceux d'une certaine classe(?) est-ce que ça signifie qu'on sait déduire un algoritme pour tous les problèmes de cette classe à partir d'un seul? par exemple, supposons que l'algoritme de Djar permette de trouver un ensemble minimal de sommets déconnectant un graphe en un temps polynomial, est-ce qu'on peut en déduire un algoritme polynomial pour le problème du représentant de commerce? ou bien on sait juste qu'un tel algoritme existe?

[inviteffe0e9ef]

Par contre, j'ai oublie de preciser que je n'ai demontre ma formule seulement pour des graphes non orientes. Mais normalement, ca fonctionne aussi bien. Dois-je considerer que ton graphe est oriente ?

[inviteffe0e9ef]

je ne connais pas bien cette question de P=NP mais si j'ai bien compris, si c'est vrai pour un problème, c'est vrai pour tous ceux d'une certaine classe(?) est-ce que ça signifie qu'on sait déduire un algoritme pour tous les problèmes de cette classe à partir d'un seul? par exemple, supposons que l'algoritme de Djar permette de trouver un ensemble minimal de sommets déconnectant un graphe en un temps polynomial, est-ce qu'on peut en déduire un algoritme polynomial pour le problème du représentant de commerce? ou bien on sait juste qu'un tel algoritme existe?

Si un probleme NP complet tombe, tous les autres tombent...
Mais ca ne veut pas dire que mon algo "serait" une solution a tous les autres. Ca veut simplement dire qu'il existe une solution polynomiale pour tous les problemes NP Complets...

Bon je retourne en cours moi ! A bienvite !

[inviteffe0e9ef]

Je me demande : Combien de temps met ton algorithme pour donner la réponse si je te donne une clique à n sommets ?

J'ai calcule ca, mais mauvaise nouvelle: c'est pas genial a cause d'un petit truc que je dois optimiser.

La complexite est: n! + n²

Le petit truc a optimiser est: comment savoir le nombre de chaines simples issues d'un vertex x ?

[Sylvestre]

La complexite est: n! + n²
Le petit truc a optimiser est: comment savoir le nombre de chaines simples issues d'un vertex x ?

C'est quoi une chaîne simple ?

[inviteffe0e9ef]

C'est quoi une chaîne simple ?

C'est un "chemin" qui te permet d'aller du sommet x a un autre y sans passer deux fois par le meme.

[Sylvestre]

Le petit truc a optimiser est: comment savoir le nombre de chaines simples issues d'un vertex x ?

En quoi le fait de savoir ceci te permettrait d'aller plus vite ? Dans le cas d'une clique tu vas trouver (n-1)! pour chaque sommet.

[inviteffe0e9ef]

En quoi le fait de savoir ceci te permettrait d'aller plus vite ? Dans le cas d'une clique tu vas trouver (n-1)! pour chaque sommet.

Mon algo repose la dessus...

[inviteffe0e9ef]

Ha ! J'ai peut etre trouve une idee de super optimisation !

Hehe, j'ai plus d'un tour dans mon sac ! Bon je vais ameliorer ca.

[Sylvestre]

Ha ! J'ai peut etre trouve une idee de super optimisation !

Hehe, j'ai plus d'un tour dans mon sac ! Bon je vais ameliorer ca.

Bravo, mais à mon avis tu ferais mieux de prouver que ce que tu as déjà est polynomial dans tous les cas de figures. Cela suffit amplement pour devenir très célèbre.

[inviteffe0e9ef]

Attends... Tu veux dire que meme si j'ai une factorielle, ce n'est pas si grave ? Cela veut dire que ce serait polynomial quand meme ?!!? Ce serait super parce que la demo est deja faite !