Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Discussion :
Calcul du flot maximal pour un graphe contenant des capacités sur les sommets
Bonjour,
je suis entrain de traiter un sujet d'examen et je bloque sur un exercice ou on me demande de calculer le flot maximal dans un graphe orienté sachant que les sommets de ce graphe ont des capacités (je sais le faire avec des capacités seulement sur les arcs).
quelqu'un peut me donner une idée .sachant que j'ai pensé à mettre des bornes sur les arcs (des intervalles).
Une idée à vérifier : en éclatant chaque sommet en un couple de deux sommets reliés par un arc de capacité "la capacité du sommet éclaté" ? Les autres arcs ayant une capacité de 0.
« La science informatique n'est pas plus la science des ordinateurs que l'astronomie n'est celle des télescopes. » — Edsger Dijkstra
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Répondre avec citation
Partager