Graphe : calcul du passage maximal sur un arc

Bonjour,

J'ai un probleme pour lequel je n'arrive pas à trouver d'algorithme standard, mais je suppose qu'il doit en exister un :

Si on a un graph du genre a->b->c, 'a' est l'entrée et 'b' la sortie. Si la capacité maximal du premier arc est 2 mais que la capacité maximale du second est 1, tout chemin de a vers c ne pourra emprunter qu'une seule fois le premier arc (meme si sa capacité est 2). Je cherche donc a calculer "l'empruntabilité" maximale des arcs. Je travail sur des 1 graphes connexes, qui peuvent comprendre des cycles ou des cycles imbriqués.

Quelqun peut-il me dire s'il existe un algorithme connu pour ce probleme ? Au niveau performances, mes graphes auront rarement plus de 100 sommets (300 grand maximum), et 5 ou 10 secondes de calcul sont acceptables.

Merci,
John.

Bonjour,

je ne suis pas spécialiste des graphes, mais ce que tu cherches est un problème classique de "flots et tensions sur les graphes".
Fais donc une recherche sur le sujet, les algos viendront avec ;)

C'est un problème de flot max/coupe min, problème classique pour lequel tu trouveras effectivement des solutions facilement, problème facile en plus (au sens complexité). Par contre, il va falloir que tu casses les cycles de tes graphes (ces algos ont pour prérequis d'avoir des graphes acycliques en entrée).