Théorie des graphes

bonjour,

y a t-il une méthode pour trouver le nombre de toutes les chaines dans un graphe

Tu peux essayer de googler "number of paths in a graph" ou "list all paths graph".

Exemple de liens :

• http://stackoverflow.com/questions/5...trary-vertices
• http://stackoverflow.com/questions/9...rected-graph-c
• http://www.codeproject.com/Answers/1...n-a-graph.aspx

Sinon comme cela j'utiliserais la somme des A^i, avec

• i indice de sommation allant de 0 au nombre de noeuds du graphe ;
• A est la matrice d'adjacence du graphe.

et pour le nombre de chaines on transformera le graphe en graphe non orienté

Citation:

---

Envoyé par aljabr

et pour le nombre de chaines on transformera le graphe en graphe non orienté

---

Pourquoi ?

Sinon l'idée de la somme des A^i n'est qu'une piste, mais je ne sais pas du tout si cela est correct pour ton problème. Notamment, il faut faire attention aux cycles. Mais je serais étonné qu'il n'y ait rien d'intéressant sur Google avec les mots clés que je t'ai donnés.

merci

j'ai trouvé pas mal de sites intéressants sur le google mais les méthodes présentées sont un peu compliquées pour être appliquées manuellement

par exemple j'ai trouvé cet algorithme

path // is a stack (initially empty)
seen// is a set
def stuck(x)
if x == t
return False
for each neighbor y of x
if y not in seen
insert y in seen
if !stuck(y)
return False
return True
def search(x)
if x == t
print path
seen = set(path)
if stuck(x)
return
for each neighbor y of x
push y on the path
search(y)
pop y from the path

Here search does the exhaustive search and stuck could be implemented in DFS style (as here) or in BFS style.

On insert le code dans des balises CODE pour plus de lisibilité.

Et l'algo que tu présente n'a rien de compliqué, exécute le sur des exemples simple à la main et tu trouveras vite leur logique.