besoin d'aide a propos d'un petit algo

[invite9f37bb98]

Bonjour,
jai besoin dun petit coup de pouce a propos dun algorithme.
Dans un graphe on veut detecter si une arete est un "isthme" (arete indispensable pourla connexite du graphe) ou pas pour cela on utilise le theorem suivant:
<si T est un arbre couvrant issu dun parcour en profondeur dun graphe connexe G alors {xy} avec date_visite[x]<date_visite[y] est un isthme si et seulement si {xy} est une arete de T et plus_bas[y]>date_viste[x]
tel que plus_bas[y] est le minimum de:

• date_visite[y].
• date_visite[y] ou t est un sommet tel que {yt} est une arte de G mais pas de T
• plus_bas[r] pour tout sommet r est un fils de y dans T

je cherche un algorithme qui calclue l'entier plus_bas pour chake sommet...voila ce qujai fais mais je croi ke ce n'est pas correct:
fonction plus_bas(s:sommet) : entier
indice<-date_visite(s);
H-difference__graphe(G,T); (T larbre issu du parcour en profondeur)
fils,_sucesseurs(H,s);
pour j allant de 0 a taille(fils)-1 faire
si (date_visite(fils[j]) < indice) alors
indice<-date_visite(fils[j]);
finsi
finpour
fils<-successeurs(T , s);
pour j allant de 0 a taille(fils)-1 faire
si (indice > plus_bas(fils[j])) alors
indice<-plus_bas(fils[j]);
finsi
finpour
retourner indice


merci davance.

PS:c'est tres unrgent SVP
-----

[invitec7217a00]

Bonjour,
Pour moi ce code a l'air de correspondre à ce que tu dis, qu'est-ce qui te fait penser qu'il n'est pas correct?

• date_visite[y] ou t est un sommet tel que {yt} est une arte de G mais pas

correction : tu veux dire date_visite[t].

[JPL]

Petite remarque : si tu avais mis ton pseudo-code dans la balise Code tu aurais gardé l'indentation ce qui aurait été plus lisible.

[invite9f37bb98]

ouai ced-29 c'est ce que je voulais dire...en fait pour l'algo j'ai pas reussi à evaluer sa complexité en temps et c'est un problème car je sais pas commbien de temps il va mettre pour faire ses calculs sil sagit d'un nombre important de sommets.
merci pour ta réponse

[A voir en vidéo sur Futura]

[invitec7217a00]

Oui c'est sûr que ton algo ne semble pas super optimisé.
Il revient en fait à refaire un parcours en profondeur de T en testant a chaque fois si le sommet a un voisin dans G tel que l'indice du deuxième sommet soit inférieur à celui du premier.
Je n'ai rien contre ça, mais je suis gêné par cette ligne :

H-difference__graphe(G,T); (T larbre issu du parcour en profondeur)

Je pense que ce calcul est très coûteux (je dirais avec du O(n), dis-moi si je me trompe), et le fait que tu le répêtes à chaque appel récursif le fait monter à O(n²).
A ce prix là tu ferais mieux de faire le calcul sur successeurs(G,s), ou alors passer H en paramètre de ta fonction et le calculer une fois pour toutes.

[invite9f37bb98]

Pour le probleme que je suis en train de resoudre les sommets sont stokes dans une pile avec leurs dates de visite dans l'acces a la date de visite d'un sommet se fait en temps constant.et je crois que tu as raison a propos de H et il vaut la definir comme variable globale avant la fonction plus_bas[s].
Est ce qu'en faisant ca on diminue le temps de calcul ou pas?
merci

[invitec7217a00]

Pour le probleme que je suis en train de resoudre les sommets sont stokes dans une pile avec leurs dates de visite dans l'acces a la date de visite d'un sommet se fait en temps constant.et je crois que tu as raison a propos de H et il vaut la definir comme variable globale avant la fonction plus_bas[s].
Est ce qu'en faisant ca on diminue le temps de calcul ou pas?
merci

Bien oui c'est exactement ce que j'ai dit ^^.
Pour un nombre très important de sommets je pense que la différence au temps d'exécution sera très perceptible.
Mais je me demande si ce ne serait pas encore plus simple de savoir si c'est un isthme en faisant une méthode légèrement modifiée de ta méthode de calcul d'arbre couvrant...

[invite9f37bb98]

je connais pas d'autre methode qui permettent de detecter les isthme...ca m'enerve..
Si tu tombe sur une autre methode merci de me tenir au courant.
Cordialement

[invite9f37bb98]

je crois qu'on peut utiliser cette proposition:
u est un isthme <==> u n'appartient a aucun cycle
qu'est ce que t'en penses?

[invitec7217a00]

Eh bien moi ce que je disais c'est que ça me parait plus simple de partir de l'algo de parcours en profondeur, tu pars de s dans G, tu marque les deux sommets de l'isthme présumé comme déjà vus, et tu parcoures ensuite en profondeur jusqu'à ce que tous les sommets soient marqués ou que tu trouve un sommet y tel que date_visite[y]<dateVisite[s].

Qu'est-ce que tu en penses?

[invitec7217a00]

je crois qu'on peut utiliser cette proposition:
u est un isthme <==> u n'appartient a aucun cycle
qu'est ce que t'en penses?

Ca revient au même, ta fonction précédente part aussi de ce principe. Mais en fait tu exploites le fait que tes sommets sont numérotés lors de la création de ton arbre. ça te simplifie la tâche car tu cherche un sommet z tel que date_visite[z]<dateVisite[x] au lieu de chercher à retrouver x absolument, ce qui sera plus long.

[invitec7217a00]

un sommet y tel que date_visite[y]<dateVisite[s].

oui j'aurais dû dire un sommet z tel que date_visite[z]<date_visite[x] mais je me suis un peu embrouillé entre la notation de ton code et de ton énoncé

[invite9f37bb98]

cette algorithme c'est pour detecter les cycles non?

[invitec7217a00]

Tout ce qu'on écrit depuis le début a pour but d'identifier un cycle passant par l'arête {xy}. C'est le seul moyen d'identifier un isthme.

[invite9f37bb98]

ok
merci pour ton aide

[invite9f37bb98]

Bonjour,
est ce que tu peux detailler ton idée encore plus stp?
Cordialement

[invitec7217a00]

fonction estUnIsthme(x,y : sommet) retourne booleen

pour tout sommet s de G faire
   marqué[s] <- faux
fin pour

aTraiter <- vide

si date_visite[x] < date_visite[y] faire
   aTraiter.empile(y);
sinon faire
   aTraiter.empile(x);
fin si

marqué[x] <- vrai
marqué[y] <- vrai
trouve <- faux

tant que nonVide(aTraiter) et trouve = faux faire
   z <- aTraiter.depile()
   marqué[z] <- vrai
   pour tout voisin v de z dans G  et tant que trouve = faux faire
      si date_visite[v] < date_visite[y] faire
         trouve <- vrai
      sinon si marqué[v] = faux faire
         marqué[v] <- vrai
         aTraiter.empile[v]
      fin si
   fin pour
fin tant que

retourner trouve

Voilà ce que ça donne en détaillé ^^
Qu'est-ce que tu en dis?