[graphe]creation de sous graphe

bonjour
j'ai un petit probleme
j'ai faut un algorithme qui cree un sous graphe??
on suppose qu'on a un graphe, et l'utilisateur marque une une transtion dans ce graphe, le sous c le graphe qui contient que les chemins passant par la transitions que l'utilisateur a marque
est-ce que vous savez si il existe un algorithme qui fait cela qui est defini
parce que le mien j'ai l'impression que c'est une usine a GAZ
merci

Citation:

---

Envoyé par deeal

le sous c'est le graphe qui ne contient que les transitions passant par ce sous graphe

---

C'est sympa comme définition récursive, mais ca nous aide pas à savoir quel sous-graphe tu veux 8O

desole je voulais dire que le sous graphe qu'on cree, tout les chemins qu'il contient passent surement par cette transitions

bien sure mon graphe il a un etat final et un etat debut
donc tout les chemins que je peux generer passent obligatoirement par cette transitions ( que l'utilisateur a marque)

Citation:

---

Envoyé par deeal

desole je voulais dire que le sous graphe qu'on cree, tout les chemins qu'il contient passent surement par cette transitions

bien sure mon graphe il a un etat final et un etat debut
donc tout les chemins que je peux generer passent obligatoirement par cette transitions ( que l'utilisateur a marque)

---

D'accord, c'est plus clair comme ça :wink: . Tu parles d'état final et d'un état de début: c'est un graphe ou un automate ? C'est un graphe avec deux sommets qu'on considère comme étant le départ et la fin des chemins ?

Ton graphe est-il orienté ?

Si il ne l'est pas: fastoche, tu as juste à prender la composante connexe d'un des sommets de la transition (vu qu'ils appartiennent à la même). Et pour ca, un petit parcours en profondeur. Evidemment, il faut vérifier que tes sommets de départ et d'arrivée sont dans cette composante connexe, et j'admet que tu acceptes les boucles sur tes parcours.

Dans le cas orienté: c'est plus chiant déjà. Supposons que tu choississe l'arc A -> B. Je verrais bien un parcours en largeur depuis le sommet de départ: chaque fois que tu tombes sur A dans ton parcours en largeur, tu remontes ton arbre de parcours (qu'il faut donc sauvegarder d'une manière ou d'une autre .. par exemple, pour chaque sommet sauvegarder le père) en notant que chacun des sommets croisés lors de la remonté appartient à ton sous-graphe. Tu fais ensuite la même depuis le sommet final, mais à la place de prendre les transitions du graphe, tu prends les transitions inverses. Et là, chaque fois que tu croises B, hop tu remontes.